Submission #1155398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155398		QwertyPi	Treasure (IOI24_treasure)	C++20	100 / 100	228 ms	5328 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> point;
const LL MAX = 5e8 + 11;

vector<int> encode(vector<pair<int, int>> P) {
    int N = P.size();
    vector<pair<int, int>> R;
    vector<int> to_send;
    for (int i = 0; i < P.size(); i++) {
        auto [x, y] = P[i];
        R.push_back({x, i});
        R.push_back({y + MAX, i});
        to_send.push_back(x);
        to_send.push_back(y + MAX);
    }
    sort(R.begin(), R.end());
    int base = MAX * 2;
    for (auto [pos, i] : R) {
        if (pos < MAX) { // x
            auto [x, y] = P[i];
            int pos_y = lower_bound(R.begin(), R.end(), pair<int, int>{y + MAX, i}) - R.begin() - N;
            to_send.push_back(base + pos_y);
            base += pos_y;
        }
    }
    return to_send;
}

vector<pair<int, int>> decode(vector<int> S) {
    sort(S.begin(), S.end());
    int N = S.size() / 3;
    vector<int> X(S.begin(), S.begin() + N);
    vector<int> Y(S.begin() + N, S.begin() + N * 2);
    vector<pair<int, int>> ans;
    int base = MAX * 2;
    for (int i = 0; i < N; i++) {
        ans.push_back({X[i], Y[S[N * 2 + i] - base] - MAX});
        base = S[N * 2 + i];
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 21 / 21
• Subtask 2: 79 / 79