Submission #1099750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099750		model_code	Treasure (IOI24_treasure)	C++17	81 / 100	352 ms	8652 KiB

treasure

// partially_correct/mb_80.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<vector<int> > a(points.size(),vector<int>(2));
	for(int i=0;i<(int)points.size();i++)
		a[i][0]=points[i].first,a[i][1]=points[i].second;
	for(int i=0;i<(int)a.size()*2;i++) vis[i]=0;
	vector<int> nums;
	int CON=(1<<30)-2;
	for(int i=0;i<(int)a.size();i++)
	{
		for(int j=0;j<2;j++)
		{
			nums.push_back(a[i][j]&CON);
		}
	}
	sort(nums.begin(),nums.end());
	vector<int> res=nums;
	for(int i=0;i<(int)a.size();i++)
	{
		int x=lower_bound(nums.begin(),nums.end(),a[i][0]&CON)-nums.begin();
		int y=lower_bound(nums.begin(),nums.end(),a[i][1]&CON)-nums.begin();
		while(vis[x]) x++;
		while(vis[y]) y++;
		vis[x]=1; vis[y]=1;
		int b=(a[i][0]&1)<<1;
		b|=(a[i][1]&1);
		// (x) 0 (y|2) b 1
		int p1=y>>9,p2=(y&((1<<9)-1));
		int v1=(x<<11)|(0<<10)|(p1<<1)|(a[i][0]&1);
		int v2=(x<<11)|(1<<10)|(p2<<1)|(a[i][1]&1);
		v1=(v1<<1)|1; v2=(v2<<1)|1;
		res.push_back(v1);
		res.push_back(v2);
	}
	return res;
}

vector<pair<int,int>> decode(vector<int> em)
{
	vector<int> nums,inf;
	for(int i=0;i<(int)em.size();i++)
	{
		if((em[i]&1)) inf.push_back(em[i]>>1);
		else nums.push_back(em[i]);
	}
	sort(nums.begin(),nums.end());
	sort(inf.begin(),inf.end());
	assert(inf.size()%2==0);
	vector<pair<int,int>> res;
	for(int i=0;i<(int)inf.size();i+=2)
	{
		int x=(inf[i]>>11);
		int y=(inf[i]>>1)&((1<<9)-1);
		y<<=9;
		y|=(inf[i+1]>>1)&((1<<9)-1);
		int vx=nums[x],vy=nums[y];
		vx|=(inf[i]&1); vy|=(inf[i+1]&1);
		res.push_back({vx, vy});
	}
	return res;
}

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