Submission #1341885

#TimeUsernameProblemLanguageResultExecution timeMemory
1341885SulABroken Line (IOI19_line)Text
0 / 100
0 ms0 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define all(a) (a).begin(), (a).end()
#define popcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;

bool in_range(int l, int r, int x) { return l < x && x < r; }

vector<pair<int,int>> solve(int n, int *X, int *Y) {
    vector<pair<int,int>> points;
    points.reserve(2*n + 1);
    for (int i = 0; i < n;) {
        if (i+2 <= n) {
            if (in_range(X[i], X[i+2], X[i+1])) {
//                cout<<"YES\n";
                points.emplace_back(X[i], Y[i+1]);
                points.emplace_back(X[i+2], Y[i+1]);
                points.emplace_back(X[i+2], Y[i+2]);
                i += 2;
            } else if (in_range(Y[i], Y[i+2], Y[i+1])) {
                points.emplace_back(X[i+1], Y[i]);
                points.emplace_back(X[i+1], Y[i+2]);
                points.emplace_back(X[i+2], Y[i+2]);
                i += 2;
            } else goto OTHER_CASE;
        } else {
            OTHER_CASE:
            points.emplace_back(X[i+1], Y[i]);
            points.emplace_back(X[i+1], Y[i+1]);
            i++;
        }
    }
    return points;
}

mt19937 f(chrono::high_resolution_clock::now().time_since_epoch().count());
int N[] = {20, 600, 5000, 50'000, 72'018, 91'891, 100'000, 100'000, 100'000, 100'000};

int main() {
    for (int n : N) {
        cout << n << " " << 3*(n+1)/2 << "\n";
    }
    int n; cin >> n;
    int x[n+1]{}, y[n+1]{};
    for (int i = 1; i <= n; cin >> x[i] >> y[i++]);
    map<int,int> XtoY;
    for (int i = 0; i <= n; i++)
        XtoY[x[i]] = y[i];
    int ptr = 0;
    for (auto [X, Y] : XtoY) {
        x[ptr] = X;
        y[ptr++] = Y;
    }
    vector<pair<int,int>> points = solve(n, x, y);
    cout << points.size() << "\n";
    for (int i = 0; i < points.size(); i++)
        cout << points[i].first << " " << points[i].second << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...