Submission #155638

#	Time	Username	Problem	Language	Result	Execution time	Memory
155638		Berted	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	357 ms	207072 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <deque>
#define ll long long
using namespace std;
bool skp[300021]={};
int fwk[300021]={},n,pr=0;
deque<int> v[300021]={};
ll rs = 0;
int qry(int x)
{
	x = n+1 - x;
	int to = 0;
	for (;x;x-=x&(-x)) {to+=fwk[x];}
	return to;
}
void upd(int x,int v)
{
	x = n+1 - x;
	for (;x<=n;x+=x&(-x)) {fwk[x]+=v;}
}
long long count_swaps(vector<int> s) 
{
	n = s.size();
	for (int i=0;i<s.size();i++) {v[s[i]+n].push_back(i+1);upd(i+1,i+1);upd(i,-i-1);}
	int i=0;
	while (pr<n)
	{
		while (skp[i]) {i++;}
		//cout<<i+1<<" "<<v[-s[i]+n].front()<<" "<<qry(v[-s[i]+n].front())<<" "<<qry(i+1)<<"\n";
		skp[v[-s[i]+n].front()-1] = 1;
		rs += (ll)qry(v[-s[i]+n].front()) - (ll)(qry(i+1)+(s[i]<0));
		upd(v[-s[i]+n].front(),1);
		v[s[i]+n].pop_front();
		v[-s[i]+n].pop_front();
		i++;
		pr += 2;
	}
	return rs;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<s.size();i++) {v[s[i]+n].push_back(i+1);upd(i+1,i+1);upd(i,-i-1);}
               ~^~~~~~~~~

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