Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created May 4, 2015 06:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jiunbae/57ee3cc1bd89bc89de64 to your computer and use it in GitHub Desktop.
Save jiunbae/57ee3cc1bd89bc89de64 to your computer and use it in GitHub Desktop.
#include<vector>
#include<stack>
#include<algorithm>
#include<iostream>
#include<functional>
using namespace std;
template <typename type> void vector_in(vector<type> * vec, int count)
{
for (int i = 0; i < count; i++)
{
int temp;
std::cin >> temp;
vec->push_back(temp);
}
}
template <typename type> void vector_out(std::vector<type> vec)
{
for (int i = 0; i < vec.size(); i++)
std::cout << vec.at(i) << ",";
std::cout << endl;
return;
}
template <typename type> void swap(type *a, type *b)
{
if (*a - *b)
*a ^= *b ^= *a ^= *b;
}
int main(int argc, char * argv[])
{
int number, temp = 0, ary[100001] = { 0, };
std::cin >> number;
std::vector<int> vec_a, vec_b;
for (int i = 0; i < number; i++)
{
vector_in(&vec_a, 1);
vector_in(&vec_b, 1);
}
for (int i = 0; i < number; i++)
for (int j = 0; j < number; j++)
if (vec_a.at(i) < vec_a.at(j))
{
swap(vec_a[i], vec_a[j]);
swap(vec_b[i], vec_b[j]);
}
vector<int> vec;
for_each(vec_b.begin(), vec_b.end(), [&ary, &vec, &temp](int n)
{
if (vec.empty() || vec.back() < n)
{
vec.push_back(n);
ary[vec.back()] = vec.size() > 1 ? vec[vec.size() - 2] : -1;
}
else
{
for (temp = 0; temp < vec.size(); temp++)
if (vec[temp] > n) break;
swap(vec[temp], n);
ary[vec[temp]] = temp > 0 ? vec[temp - 1] : -1;
}
});
cout << number - vec.size() << endl;
temp = vec.back();
do{
for (int i = 0; i < vec_b.size(); i++)
if (vec_b[i] == temp)
{
vec_b[i] = 0;
break;
}
} while (1 + (temp = ary[temp]));
for_each(vec_a.begin(), vec_a.end(), [&vec_b](int n){static int t = 0; if (vec_b[t]) cout << n << endl; t++; });
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment