Submission #815694

#	Time	Username	Problem	Language	Result	Execution time	Memory
815694		Edu175	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	300 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto sdg:v)cout<<sdg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

vector<ll>a,p,pos; // permutation, position of idx
void move(ll i, ll j){ //move i to pos j by swapping j<i
	//cout<<"move "<<i<<" "<<j<<"\n";
	while(j<pos[i]){
		ll &ant=p[pos[i]-1];
		swap(pos[ant],pos[i]);
		swap(ant,p[i]);
	}
}
long long count_swaps(vector<int> S){
	for(auto i:S)a.pb(i);
	ll n=SZ(a)/2;
	fore(i,0,2*n)p.pb(i),pos.pb(i);
	vector<ll> l[n+1],r[n+1];
	ll res=0;
	fore(i,0,2*n){
		ll s=abs(a[i]);
		//cout<<i<<" "<<a[i]<<": "<<s<<"\n";
		//imp(p); imp(pos);
		if(a[i]<0){
			//cout<<"l\n";
			//imp(r[s]);
			if(!SZ(r[s]))l[s].pb(i);
			else {
				ll j=r[s].back(); r[s].pop_back();
				res+=i-pos[j];
				move(i,pos[j]);
			}
		}
		else {
			//cout<<"r\n";
			//imp(l[s]);
			if(!SZ(l[s]))r[s].pb(i);
			else {
				ll j=l[s].back(); l[s].pop_back();
				res+=i-(pos[j]+1);
				move(i,pos[j]+1);
			}
		}
		/*fore(i,0,n+1){
			cout<<"l["<<i<<"]: "; imp(l[i]);
			cout<<"r["<<i<<"]: "; imp(r[i]);
		}*/
	}
	return res;
}

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