Submission #427236

#	Time	Username	Problem	Language	Result	Execution time	Memory
427236		dreezy	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	261 ms	142952 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pb push_back
#define pi pair<int,int>

const int maxn = 2e5 + 5;

struct SegTree{
	int st[maxn * 4];
	int sz;
	void init(){
		sz = maxn;
		memset(st, 0, sizeof st);
	}
	
	
	void upd(int n, int l, int r, int ind, int val){
		if(l == r){
			st[n] = val;
			return;
		}
		
		int mid = (l + r)/2;
		
		if( ind <= mid)
			upd(2* n + 1, l, mid, ind, val);
		else
			upd(2*n +2, mid +1, r,ind, val);
		st[n] = st[2*n+1] + st[2* n + 2];
	}
	void insert(int val ){
		upd(0,1, sz, val+1, 1);
		
	}
	void erase(int val){
		upd(0,1, sz, val+1, 0);
	}
	
	int qry(int n, int l, int r, int s, int e){
		if( e < s) return 0;
		
		if( s <= l and e >= r) return st[n];
		
		int ans = 0;
		int mid = (l + r) /2;
		if( s <= mid)
			ans+=qry(2 * n + 1, l ,mid, s, e);
		if( e > mid)
			ans += qry(2* n+2, mid + 1, r, s,e);
		return ans;
	}
	
	
	int getind(int val){
		return qry(0, 1,sz,1, val);
	}
};

SegTree shoes;

long long count_swaps(vector<int> s) {
	
	ll ans = 1e18;
	int n = s.size();
	vector<pi> lefts(n/2);
	int cntleft = 0;
	vector<pair<int, pi>> sortlefts(n/2);
	
	vector<queue<int>> rightinds(n);
	shoes.init();
	for(int i =0; i<n ;i++){
		shoes.insert(i);
		if(s[i] > 0){
			rightinds[s[i]].push(i);
		}
	}
	for(int i =0; i<n; i++){
		if(s[i] < 0){
			int firstright = rightinds[-s[i]].front();
			rightinds[-s[i]].pop();
			lefts[cntleft++] = {i, firstright};
			sortlefts[cntleft - 1] = {i+firstright, {i, firstright}};
		}
	}
	
	sort(sortlefts.begin(), sortlefts.end());
	
	for(int i =0; i<n/2; i++){
		lefts[i] = sortlefts[i].second;
	}
	

	ll posans = 0;
	vector<int> inds(n);
	for(int i =0; i<n ;i++) inds[i] = i;

	//for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl;
	int l = 0;
	
	for(pi shoe : lefts){
		//get first availabe

		int leftind = shoe.first;
		int rightind = shoe.second;
		//cout <<endl;
	
		int newleftind = 2 * l + shoes.getind(leftind);
		
		ll dist1 = abs(newleftind - 2 * l);
		
		
		shoes.erase(leftind);
		int newrightind = 2 * l + 1 + shoes.getind(rightind);

		//cout <<leftind<<", "<<rightind<<": "<< newleftind<<", "<<newrightind<<endl;
		
		ll dist2 = abs(newrightind -( 2 * l + 1));
		shoes.erase(rightind);
		/*for(int ss : shoes){
			cout <<ss<<", ";
		}
		cout <<endl;
		*/
		//cout << inds[lefts[l]]<<", "<<inds[firstright]<<": ";
		
		//cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl;
		posans += dist1 + dist2;
		l++;
	}
	
	ans = min(ans, posans);
	
	//cout << posans<<endl<<endl;
		
	
	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