Submission #1226128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226128		bynix	Treasure (IOI24_treasure)	C++20	100 / 100	367 ms	10932 KiB

treasure

#include "bits/stdc++.h"
#include "treasure.h"
using namespace std;

vector<int> encode(vector<pair<int, int>> P) {
  vector<int> ans, y;
  
  for (auto &e: P) y.push_back(e.second);
  sort(y.begin(), y.end());
  sort(P.begin(), P.end());
  map<int, int> ymap;
  int c = 0;
  for (auto &e: y){if (!ymap.count(e)) ymap[e] = c, c++;}
  
  int cs = 0;
  for (auto &e: P) {
    cs += ymap[e.second];
    ans.push_back(cs);
    ans.push_back(e.first + 1e9 - 1);
    ans.push_back(e.second + 1e9 + 5e8);
  }

  return ans;
}

vector<pair<int, int>> decode(vector<int> S) {
  vector<int> x, y, pref;
  for (auto &e: S){
    if (e >= 1e9 + 5e8) y.push_back(e - 1e9 - 5e8);
    else if (e >= 1e9 - 1) x.push_back(e - 1e9 + 1);
    else pref.push_back(e);
  }
  
  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  int c = 0;
  map<int, int> ymap, ym;
  for (auto &e: y){
    if (!ymap.count(e)) ymap[e] = c, c++;
    ym[c] = e;
  }

  vector<pair<int, int>> ans;
  int n = x.size();
  for (auto &e: x) ans.push_back({e, 0});

  sort(pref.begin(), pref.end());
  ans[0].second = ym[pref[0] + 1];
  for (int i = 1; i < n; i++) ans[i].second = ym[pref[i] - pref[i - 1] + 1];

  return ans;
}

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