Submission #1104603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104603		Nonoze	Treasure (IOI24_treasure)	C++17	100 / 100	327 ms	6856 KiB

treasure

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

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)



vector<int> encode(vector<pair<int, int>> a) { int n=sz(a);
	vector<int> b;
	vector<pair<int, int>> x, y;
	for (int i=0; i<n; i++) {
		b.push_back(a[i].fi), b.push_back(5e8+a[i].se);
		x.pb({a[i].fi, i}), y.pb({a[i].se, i});
	}
	sort(all(x)), sort(all(y));
	vector<int> emply(n);
	for (int i=0; i<n; i++) emply[y[i].se]=i;
	int cnt1=0, cnt2=0;
	for (int i=0; i<n-1; i++) {
		int act=emply[x[i].se], nxt=emply[x[i+1].se];
		if (act<nxt) cnt1++;
		else cnt2++;
	}
	vector<int> vec;
	for (int i=0; i<n; i++) {
		if (cnt1>=cnt2) vec.pb(emply[x[i].se]);
		else vec.pb(n-emply[x[i].se]-1);
	}
	int cnt=0;
	for (int i=0; i<n; i++) {
		if (i==n-1 && cnt2>cnt1) cnt++;
		int val=cnt*n+vec[i];
		b.push_back(1e9+val);
		if (i<n-1 && vec[i]>vec[i+1]) cnt++;
	}
	assert(b.back()<=2e9);
	return b;
}

vector<pair<int, int>> decode(vector<int> a) {
	int m=sz(a), n=sz(a)/3;
	sort(all(a));
	vector<int> x, y, empl, empl2;
	for (int i=0; i<m; i++) {
		if (i<n) x.pb(a[i]);
		else if (i<2*n) y.pb(a[i]-5e8);
		else  empl.pb(a[i]-1e9);
	}
	vector<int> ansx, ansy;
	int prec=0, precj=0, i=0;
	bool rev=0;
	for (auto u: empl) {
		int j=u%n;
		int div=u/n;
		ansx.pb(x[i]), ansy.pb(j);
		if (div-prec>1) rev=1;
		if (i==n-1 && div==prec+1 && precj<=j) rev=1;
		i++;
		prec=u/n, precj=j;
	}
	sort(all(y));
	vector<pair<int, int>> ans;
	if (rev) for (auto &u: ansy) u=y[n-u-1];
	else for (auto &u: ansy) u=y[u];
	for (int i=0; i<n; i++) ans.pb({ansx[i], ansy[i]});
	return ans;
}

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