| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 731434 | danikoynov | Sky Walking (IOI19_walk) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void input_file()
{
freopen("03.in", "r", stdin);
freopen("03.out", "w", stdout);
}
const int maxn = 1e5 + 10;
struct point
{
int x, y;
point(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
};
int n;
point d[maxn];
void print_point(point p)
{
cout << p.x << " " << p.y << endl;
}
bool cmp(point p1, point p2)
{
return p1.x < p2.x;
}
int used[maxn], len[maxn], f[maxn], bef[maxn];
vector < int > left_idc;
vector < int > longest_increasing()
{
int sz = 0;
len[0] = 0;
for (int i = 0; i < left_idc.size(); i ++)
{
int idx = left_idc[i];
int lf = 1, rf = sz;
///cerr << "-----------" << endl;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
///cerr << lf << " : " << rf << " : " << len[mf] << " " << d[idx].y << endl;
if (len[mf] < d[idx].y)
lf = mf + 1;
else
rf = mf - 1;
}
bef[idx] = f[lf - 1];
f[lf] = idx;
len[lf] = d[idx].y;
if (lf > sz)
sz = lf;
}
int idx = f[sz];
vector < int > sub;
while(idx != 0)
{
///cerr << idx << endl;
sub.push_back(idx);
idx = bef[idx];
}
reverse(sub.begin(), sub.end());
return sub;
}
vector < int > longest_decreasing()
{
int sz = 0;
len[0] = 2e9 + 1;
for (int i = 0; i < left_idc.size(); i ++)
{
int idx = left_idc[i];
int lf = 1, rf = sz;
///cerr << "-----------" << endl;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
///cerr << lf << " : " << rf << " : " << len[mf] << " " << d[idx].y << endl;
if (len[mf] > d[idx].y)
lf = mf + 1;
else
rf = mf - 1;
}
bef[idx] = f[lf - 1];
f[lf] = idx;
len[lf] = d[idx].y;
if (lf > sz)
sz = lf;
}
int idx = f[sz];
vector < int > sub;
while(idx != 0)
{
///cerr << idx << endl;
sub.push_back(idx);
idx = bef[idx];
}
reverse(sub.begin(), sub.end());
return sub;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> d[i].x >> d[i].y;
left_idc.push_back(i);
}
sort(d + 1, d + n + 1, cmp);
for (int i = 1; i <= n; i ++)
used[i] = 0;
int cnt = n;
vector < point > path;
point st(0, 0);
int last_step = 0, step = 0;
vector < int > bef_idc;
while(left_idc.size() > 0)
{
///cerr << "step " << ++ step << endl;
cerr << left_idc.size() << endl;
vector < int > up = longest_increasing();
vector < int > down = longest_decreasing();
cerr << "size " << max(up.size(), down.size()) << endl;
if (up.size() > down.size())
{
/**for (int v : up)
cerr << " " << v;
cerr << endl;*/
last_step = 1;
st.x = d[up[0]].x;
path.push_back(st);
if (st.y > d[up[0]].y)
{
st.y = d[up[0]].y;
path.push_back(st);
}
for (int i = 0; i < up.size(); i ++)
{
point cur = d[up[i]];
if (i % 2 == 0)
{
st.y = cur.y;
if (i + 1 != up.size())
st.y = d[up[i + 1]].y;
path.push_back(st);
}
else
{
st.x = cur.x;
if (i + 1 != up.size())
st.x = d[up[i + 1]].x;
path.push_back(st);
}
}
unordered_set < int > st;
for (int v : up)
st.insert(v);
///cerr << "type increasing " << st.size() << " : " << left_idc.size() << endl;
/**for (int v : st)
cerr << v << " ";
cerr << endl;
for (int v : left_idc)
cerr << v << " ";
cerr << endl;*/
///cerr << st.size() << endl;
vector < int > new_idc;
for (int v : left_idc)
if (st.find(v) == st.end())
new_idc.push_back(v);
left_idc = new_idc;
}
else
{
last_step = 0;
st.y = d[down[0]].y;
path.push_back(st);
if (st.x > d[down[0]].x)
{
st.x = d[down[0]].x;
path.push_back(st);
}
for (int i = 0; i < down.size(); i ++)
{
point cur = d[down[i]];
if (i % 2 == 1)
{
st.y = cur.y;
if (i + 1 != down.size())
st.y = d[down[i + 1]].y;
path.push_back(st);
}
else
{
st.x = cur.x;
if (i + 1 != down.size())
st.x = d[down[i + 1]].x;
path.push_back(st);
}
}
unordered_set < int > st;
for (int v : down)
st.insert(v);
//cerr << "type decreasing " << st.size() << " : " << left_idc.size() << endl;
vector < int > new_idc;
for (int v : left_idc)
if (st.find(v) == st.end())
new_idc.push_back(v);
left_idc = new_idc;
}
///
}
cerr << path.size() << endl;
cout << path.size() << endl;
for (point cur : path)
print_point(cur);
}
void all_cases(int to)
{
for (int cs = 4; cs <= 4; cs ++)
{
string file_name_in, file_name_out;
file_name_in = (char)(cs + '0');
file_name_in = file_name_in + ".in";
file_name_out = (char)(cs + '0');
file_name_out = file_name_out + ".out.txt";
file_name_in = "0" + file_name_in;
file_name_out = "0" + file_name_out;
if (cs == 10)
{
file_name_in = "10.in";
file_name_out = "10.out.txt";
}
cerr << "Test: " << cs << endl;
freopen(file_name_in.c_str(), "r", stdin);
freopen(file_name_out.c_str(), "w", stdout);
solve();
}
}
int main()
{
all_cases(1);
return 0;
}