Submission #1031250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031250		Lalic	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	240 ms	142516 KiB

shoes

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 2e5+10;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int N;
ll tree[MAXN];

void upd(int p){ for(;p<=2*N;p+=(p&-p)) tree[p]++; }
ll query(int p){
	ll ret=0;
	for(;p>0;p-=(p&-p)) ret+=tree[p];
	return ret;
}

void coordinateCompression(vector<int>& arr){
	vector<int> proc;
	for(auto u : arr) proc.pb(abs(u));
	
	sort(all(proc));
	proc.erase(unique(all(proc)), proc.end());
	
	map<int, int> comp;
	for(int i=0;i<(int)proc.size();i++) comp[proc[i]]=i+1;
	
	for(auto& u : arr){
		if(u<0) u=-comp[-u];
		else u=comp[u];
	}
}

ll count_swaps(vector<int> s) {
	N=((int)s.size())>>1;
	
	coordinateCompression(s);
	
	vector<queue<int>> occ(N+1), aux(N+1);
	vector<int> left;
	for(int i=0;i<2*N;i++){
		if(s[i]>0) occ[s[i]].push(i+1), aux[s[i]].push(i+1);
		else left.pb(i+1);
	}
	
	vector<pii> proc;
	for(auto u : left){
		int id=-s[u-1];
		proc.pb({u+aux[id].front(), u});
		aux[id].pop();
	}
	
	left.clear();
	
	sort(all(proc));
	for(auto [u, v]: proc) left.pb(v);
	
	
	ll ans=0;
	for(int i=0;i<N;i++){
		ll curr=left[i]-query(left[i])-1;
		upd(left[i]);
		
		int id=abs(s[left[i]-1]);
		curr+=occ[id].front()-query(occ[id].front())-1;
		upd(occ[id].front());
		occ[id].pop();
		
		ans+=curr;
	}
	
	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15