Submission #1127888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127888		ByeWorld	Treasure (IOI24_treasure)	C++17	0 / 100	240 ms	14132 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int MAXA = 1e6;
const int INF = 5e8+1;


std::vector<int> encode(std::vector<std::pair<int, int>> P) {
	map<int,vector<int>> m;
	map<int,vector<int>> idx;
	vector <int> ret;
	vector <int> x, y;
	for(auto [p, q] : P){
		m[p].pb(q);
		x.pb(p); y.pb(q);
	}
	sort(x.begin(), x.end()); sort(y.begin(), y.end());
	for(int i=0; i<y.size(); i++)
		idx[y[i]].pb(i);
	
	int ba = 2*INF;
	for(int i=0; i<x.size(); i++){
		int v = x[i];
		int oth = m[v].back(); m[v].pop_back();
		int id = idx[oth].back(); idx[oth].pop_back();
		int nw = ba + id;
		ret.pb(nw);
		ba = nw;
	}
	for(auto [p, q] : P) ret.pb(p), ret.pb(q+INF);

	return ret;
}

std::vector<std::pair<int, int>> decode(std::vector<int> S) {
	vector <int> x, y, oth; vector <pii> ans;
	for(auto in : S){
		if(in <= INF) x.pb(in);
		else if(in <= 2*INF) y.pb(in-INF);
		else oth.pb(in);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(oth.begin(), oth.end());

	int ba = 2*INF;
	for(int i=0; i<oth.size(); i++){
		int id = oth[i]-ba;
		ba = oth[i];
		ans.pb({x[i], y[id]});
	}
	return ans;
}

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