| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 433668 | kostia244 | Sky Walking (IOI19_walk) | C++17 | 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 all(x) begin(x), end(x)
using namespace std;
using ll = long long;
vector<array<int, 2>> solve(int n, vector<array<int, 2>> pts) {
set<array<int, 2>> X, Y;
for(int i = 0; i < n; i++) {
X.insert({pts[i][0], i});
Y.insert({pts[i][1], i});
}
auto del = [&](int i) {
X.erase({pts[i][0], i});
Y.erase({pts[i][1], i});
};
auto find = [&](int mode) -> array<int, 2> {
array<int, 2> v;
if(mode == 0)
v = *Y.rbegin();
if(mode == 1)
v = *X.rbegin();
if(mode == 2)
v = *Y.begin();
if(mode == 3)
v = *X.begin();
del(v[1]);
return {pts[v[1]][0], pts[v[1]][1]};
};
vector<array<int, 2>> targets;
for(int i = 0; i < n; i++) {
targets.push_back(find(i%4));
}
vector<array<int, 2>> sol;
sol.push_back({0, targets[0][1]});
for(int i = 0; i+1 < n; i++) {
int mode = i%4;
if(mode == 0) {
int y = sol.back()[1];
if(targets[i][0] > targets[i+1][0])
sol.push_back({targets[i][0], y});
sol.push_back({targets[i+1][0], y});
}
if(mode == 2) {
int y = sol.back()[1];
if(targets[i][0] < targets[i+1][0])
sol.push_back({targets[i][0], y});
sol.push_back({targets[i+1][0], y});
}
if(mode == 3) {
int x = sol.back()[0];
if(targets[i][1] > targets[i+1][1])
sol.push_back({x, targets[i][1]});
sol.push_back({x, targets[i+1][1]});
}
if(mode == 1) {
int x = sol.back()[0];
if(targets[i][1] < targets[i+1][1])
sol.push_back({x, targets[i][1]});
sol.push_back({x, targets[i+1][1]});
}
//cerr << (i%4) << " " << targets[i][0] << " " << targets[i][1] << endl;
}
sol.push_back(targets.back());
return sol;
}
template<int inv>
vector<array<int, 2>> transform(vector<array<int, 2>> a, int rx, int ry, int sw) {
return a;
if(inv && sw) swap(rx, ry);
for(auto &[x, y] : a) {
if(rx) x *= -1;
if(ry) y *= -1;
if(sw) swap(x, y);
}
return a;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<array<int, 2>> pts(n);
for(auto &[x, y] : pts) cin >> x >> y;
vector<array<int, 2>> sol = solve(n, pts);
for(int msk = 1; msk < 8; msk++) {
auto tmp = transform<1>(solve(n, transform<0>(pts, msk&1, msk&2, msk&4)), msk&1, msk&2, msk&4);
if(tmp.size() < sol.size()) sol = tmp;
}
cout << sol.size() << '\n';
for(auto [x, y] : sol) cout << x << " " << y << '\n';
}