Submission #1240644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240644		hengliao	Treasure (IOI24_treasure)	C++20	81 / 100	491 ms	14700 KiB

treasure

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

const ll mxN=4e4;

vector<int> encode(vector<pair<int, int>> P) {
	ll n=P.size();
	vector<int> re;
	vll con1, con2;
	for(auto &[x, y]:P){
		con1.pb(x);
		con2.pb(y);
	}
	sort(con1.begin(), con1.end());
	sort(con2.begin(), con2.end());
	con1.erase(unique(con1.begin(), con1.end()), con1.end());
	con2.erase(unique(con2.begin(), con2.end()), con2.end());
	
	auto id1=[&](ll tar){
		return lower_bound(con1.begin(), con1.end(), tar)-con1.begin();
	};

	auto id2=[&](ll tar){
		return lower_bound(con2.begin(), con2.end(), tar)-con2.begin();
	};

	for(auto &it:con1){
		re.pb((int) it*2);
	}
	for(auto &it:con2){
		re.pb((int) it*2+1);
	}

	auto hs=[&](ll x, ll y){
		return x*mxN+y; 
	};

	for(ll i=0;i<n;i++){
		re.pb((int) hs(id1(P[i].F), id2(P[i].S)));
		re.pb((int) hs(id1(P[i].F), id2(P[i].S)));
	}

	// for(auto &it:re){
	// 	cout<<it<<' ';
	// }

	// cout<<'\n';
	return re;
}

vector<pair<int, int>> decode(vector<int> S) {
	map<ll, ll> mp;
	for(auto &it:S){
		mp[it]++;
	}
	vll con1, con2;
	for(auto &[x, y]:mp){
		if(y%2==1){
			if(x%2==0){
				con1.pb(x/2);
			}
			else{
				con2.pb(x/2);
			}
		}
	}

	vector<pair<int, int>> re;

	for(auto &[x, y]:mp){
		if(y>=2){
			ll f=x/mxN;
			ll s=x%mxN;
			re.pb({(int) con1[f], (int) con2[s]});
		}
	}

	return re;
}	

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