Submission #169276

#	Time	Username	Problem	Language	Result	Execution time	Memory
169276		anubhavdhar	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1110 ms	276384 KiB

shoes

#include<bits/stdc++.h>

#define ll long long int 
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr(i,a,b) for(i=a;i<b;i++)
#define ii pair<ll,ll>
#define vi vector<ll> 
#define vii vector<ii>
#define ff first
#define ss second 
#define mp make_pair 
#define pb push_back

using namespace std;

#include "shoes.h"
/*
const ll MAXN = 1e5+5;
const ll INF = 1e17 + 9;
const ll MOD = 1e9 + 7;
const ll INT_BITS = 31;
const ll LOGN = 17;
*/
long long count_swaps(vector<int>s) 
{
	//cout<<"p\n";
	ll N,i,j,l,r,ans = 0;
	//cin>>N;
	N = s.size();
	ll A[N],pr[N];
	queue<ll> L[1 + N],R[N+1];
	bool rem[N];
	FOR(i,N)
	{
		A[i] = s[i];
		//cout<<"entering for i = "<<i<<endl;
		rem[i] = false;
		if (A[i] < 0) // Left shoe
		{
			if (!R[-A[i]].empty())
			{
				r = R[-A[i]].front();
				R[-A[i]].pop();
				pr[r] = i;
				pr[i] = r;
				A[i] *= -1;
				A[r] *= -1;
				ans++;
			}
			else
				L[-A[i]].push(i);
		}
		else if (A[i] > 0) // Right Shoe;
		{
			if (!L[A[i]].empty())
			{
				l = L[A[i]].front();
				L[A[i]].pop();
				pr[l] = i;
				pr[i] = l;
			}
			else
				R[A[i]].push(i);
		}
	}
    /*
	FOR(i,N)
		cout<<A[i]<<" ";
	cout<<endl;
	FOR(i,N)
		cout<<pr[i]<<" ";
	cout<<endl;
    */
	FOR(i,N)
	{
		if(A[i] < 0)
		{
			ans += pr[i]-i-1;
			for(j = i + 1;j<pr[i];j++)
				if (rem[j])
					ans--;
			rem[pr[i]] = true;
		}

	}
	return ans;
}

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