제출 #1240862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240862		hengliao	Treasure (IOI24_treasure)	C++20	0 / 100	4638 ms	8056 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;
const ll mxM=1e9+2;

vector<int> encode(vector<pair<int, int>> P) {
	ll n=P.size();
	vector<int> re;
	vector<pll> con1, con2;
	for(ll i=0;i<n;i++){
		con1.pb({P[i].F, i});
		con2.pb({P[i].S, i});
	}
	// sort(P.begin(), P.end());
	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.F*2);
	}
	for(auto &it:con2){
		re.pb((int) it.F*2+1);
	}	

	vector<pll> cor(n);

	for(ll i=0;i<n;i++){
		cor[con1[i].S].F=i;
	}

	for(ll i=0;i<n;i++){
		cor[con2[i].S].S=i;
	}

	vll perm(n);

	for(ll i=0;i<n;i++){
		ll idx=con1[i].S;
		perm[i]=cor[idx].S;
	}

	ll pt=mxM;
	ll siz=n;

	vector<bool> done(n);

	auto id=[&](ll tar){
		ll cnt=0;
		for(ll i=0;i<tar;i++){
			if(!done[i]) cnt++;
		}
		return cnt;
	};

	for(ll i=0;i<n;i++){
		re.pb(pt+id(perm[i]));
		done[perm[i]]=1;
		pt+=siz;
		siz--;
	}

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

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

vector<pair<int, int>> decode(vector<int> S) {
	vll con1, con2, con3;
	for(auto &it:S){
		if(it<mxM){
			if(it%2==0){
				con1.pb(it/2);
			}
			else{
				con2.pb(it/2);
			}
		}
		else{
			con3.pb(it);
		}
	}

	sort(con1.begin(), con1.end());
	sort(con2.begin(), con2.end());
	sort(con3.begin(), con3.end());

	ll n=con3.size();

	vector<pair<int, int>> re;

	ll pt=mxM;
	ll siz=n;

	vector<bool> done(n);

	auto f=[&](ll idx){
		ll cnt=0;
		for(ll i=0;i<n;i++){
			if(cnt>=idx && !done[i]) return i;
			if(!done[i]) cnt++;
		}
		return -1LL;
	};

	for(ll i=0;i<n;i++){
		ll cur=con3[i];
		cur-=pt;
		ll tep=f(cur);
		done[tep]=1;
		re.pb({(int) con1[i], (int) con2[tep]});
		pt+=siz;
		siz--;
	}

	return re;
	// return {0, 0};
}	

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