Submission #1031229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031229		Lalic	Arranging Shoes (IOI19_shoes)	C++17	65 / 100	152 ms	73400 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 slowcalc(vector<int> s) {
	N=((int)s.size())>>1;
	
	coordinateCompression(s);
	
	vector<vector<int>> occ(N+1);
	vector<int> left;
	for(int i=0;i<2*N;i++){
		if(s[i]<0) left.pb(i+1);
		else occ[s[i]].pb(i+1);
	}
	
	ll ans=LINF;
	do{
		vector<int> id(N+1, 0);
		for(int i=0;i<=2*N;i++) tree[i]=0;
		
		ll res=0;
		for(auto u : left){
			ll curr=u-query(u)-1;
			upd(u);
			
			int val=-s[u-1];
			//~ cout << u << "\n";
			curr+=occ[val][id[val]]-query(occ[val][id[val]])-1;
			upd(occ[val][id[val]]); id[val]++;
			
			res+=curr;
		}
		
		ans=min(ans, res);
	}while(next_permutation(all(left)));
	
	return ans;
}

ll count_swaps(vector<int> s) {
	N=((int)s.size())>>1;
	
	if(N<=8)
		return slowcalc(s);
	
	coordinateCompression(s);
	
	vector<queue<int>> occ(N+1);
	vector<int> left;
	for(int i=0;i<2*N;i++){
		if(s[i]<0) left.pb(i+1);
		else occ[s[i]].push(i+1);
	}
	
	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: 0 / 20
• Subtask 6: 0 / 15