Submission #197816

#	Time	Username	Problem	Language	Result	Execution time	Memory
197816		arnold518	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	259 ms	15900 KiB

shoes

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int S[MAXN+10], N;
vector<int> pos[MAXN+10];
bool vis[MAXN+10];
ll ans;

int tree[MAXN+10];
void update(int i) { for(; i<=N*2; i+=(i&-i)) tree[i]++; }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
int query(int l, int r) { return query(r)-query(l-1); }

ll count_swaps(vector<int> _S)
{
	int i, j;

	N=_S.size()/2;
	for(i=1; i<=2*N; i++) S[i]=_S[i-1];

	for(i=2*N; i>=1; i--) pos[S[i]+N].push_back(i);

	for(i=1; i<=2*N; i++)
	{
		if(vis[i]) continue;
		int j=pos[-S[i]+N].back();
		ans+=j-i-1-query(i, j);
		pos[S[i]+N].pop_back(); pos[-S[i]+N].pop_back();
		vis[i]=true; vis[j]=true;
		update(i); update(j);
		if(S[i]>0) ans++;
	}	
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:23:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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