Submission #1240866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240866		hengliao	Treasure (IOI24_treasure)	C++20	100 / 100	236 ms	8144 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;

namespace{
	const ll mxN=4e4;
	const ll mxM=1e9+2;
	const ll LOG=21;

	struct BIT{
		vll tree;
		ll siz;

		void init(ll sz){
			siz=sz+1;
			tree=vll(siz, 0);
		}

		void update(ll idx, ll val){
			idx++;
			for(;idx<siz;idx+=(idx&(-idx))){
				tree[idx]+=val;
			}
		}

		ll getpre(ll idx){
			idx++;
			ll re=0;
			for(;idx>0;idx-=(idx&(-idx))){
				re+=tree[idx];
			}
			return re;
		}

		ll getsum(ll a, ll b){
			return getpre(b)-getpre(a-1);
		}

		ll bs(ll tar){ // find last smaller or equal to tar
			ll sum=0;
			ll pt=0;
			for(ll i=LOG-1;i>=0;i--){
				ll add=(1LL<<i);
				if(pt+add>=siz) continue;
				if(sum+tree[pt+add]<=tar){
					pt+=add;
					sum+=tree[pt];
				}
			}
			return pt-1;
		}
	};
}



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;

	BIT bit;

	bit.init(n);

	for(ll i=0;i<n;i++){
		bit.update(i, 1);
	}

	// vector<bool> done(n);

	auto id=[&](ll tar){
		return  bit.getsum(0, tar-1);
		// 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]));
		bit.update(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;

	BIT bit;

	bit.init(n);

	for(ll i=0;i<n;i++){
		bit.update(i, 1);
	}

	// vector<bool> done(n);

	auto f=[&](ll idx){
		return bit.bs(idx)+1;
	};

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

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

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