Submission #1172001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172001		fryingduc	Treasure (IOI24_treasure)	C++20	100 / 100	249 ms	6652 KiB

treasure

#include "treasure.h"

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e4 + 4;
const int inf = 5e8 + 1;

vector<int> encode(vector<pair<int, int>> P) {
  int n = (int)P.size();
  vector<int> res;
  vector<int> tx, ty;
  set<pair<int, int>> s;
  for (int i = 0; i < (int)P.size(); ++i) {
    ty.push_back(P[i].second);
    res.push_back(P[i].first);
    res.push_back(P[i].second + inf);
  }
  sort(ty.begin(), ty.end());
  for (int i = 0; i < (int)ty.size(); ++i) {
    s.insert(make_pair(ty[i], i));
  }
  sort(P.begin(), P.end());
  int cur = inf * 2;
  for (int i = 0; i < P.size(); ++i) {
    auto it = s.lower_bound(make_pair(P[i].second, -1));
    cur += it->second;
    res.push_back(cur);
    s.erase(it);
  }
  return res;
}

vector<pair<int, int>> decode(vector<int> S) {
  vector<int> tx, ty;
  vector<int> prf;
  for (auto i : S) {
    if (i < inf) {
      tx.push_back(i);
    } else if (i < inf * 2) {
      ty.push_back(i - inf);
    } else {
      prf.push_back(i);
    }
  }
  sort(tx.begin(), tx.end());
  sort(ty.begin(), ty.end());
  sort(prf.begin(), prf.end());
  vector<pair<int, int>> res;
  int prv = inf * 2;
  for (int i = 0; i < (int)prf.size(); ++i) {
    res.emplace_back(tx[i], ty[prf[i] - prv]);
    prv = prf[i];
  }
  debug(res);
  return res;
}

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