Submission #1099746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099746		model_code	Treasure (IOI24_treasure)	C++17	100 / 100	255 ms	11264 KiB

treasure

// model_solution/me_correct.cpp

#include <bits/stdc++.h>
#include "treasure.h"
 
using namespace std;
 
const int N=2e5+5;
 
int vis[N];
 
vector<int> encode(vector<pair<int,int>> points)
{
	vector<int> x,y;
	for(int i=0;i<(int)points.size();i++)
	{
		x.push_back(points[i].first);
		y.push_back(points[i].second);
	}
	vector<vector<int> > a;
	for(int i=0;i<(int)x.size();i++)
		a.push_back({x[i],y[i]});
	int n=a.size();
	sort(a.begin(),a.end());
	vector<int> ret;
	for (int i=0;i<n;i++)
	{
		ret.push_back((int)1e9+a[i][0]);
		ret.push_back((int)1.5e9+a[i][1]);
	}
	vector<pair<int,int> > tmp;
	for (int i=0;i<n;i++)
	tmp.push_back({a[i][1],i});
	sort(tmp.begin(),tmp.end());
	int cur=0;
	for (int i=0;i<n;i++)
	{
		cur+=tmp[i].second;
		ret.push_back(cur);
	}
	return ret;
}
 
vector<pair<int,int>> decode(vector<int> em)
{
	int n=em.size()/3;
	em.push_back(0);
	sort(em.begin(),em.end());
	vector<int> p(n);
	for (int i=1;i<=n;i++)
	p[i-1]=em[i]-em[i-1];
	vector<vector<int> > v;
	for (int i=n+1;i<=2*n;i++)
	v.push_back({em[i]-(int)1e9,0});
	for (int i=2*n+1;i<=3*n;i++)
	v[p[i-2*n-1]][1]=em[i]-(int)1.5e9;
	vector<pair<int,int>> ret;
	for(int i=0;i<n;i++)
	{
		ret.push_back({v[i][0], v[i][1]});
	}
	return ret;
}

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