Submission #352363

#	Time	Username	Problem	Language	Result	Execution time	Memory
352363		David_M	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	180 ms	14444 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll f[300005],b[300005],c[300005],o=1,N;
void upd(int x){for(;x<=2*N;x+=x&(-x))f[x]+=o;}
ll get(int x, ll Ans=0){for(;x;x-=x&(-x))Ans+=f[x];return Ans;}
long long count_swaps(vector<int> s){
	ll x,ans=0;
	map<ll, ll> a;
	N=(int)s.size()/2;
	vector<ll>ss(2*N);
	for (int i=0; i<2*N; i++){
		c[s[i]+2*N]++;
		if(s[i]<0)ss[i]=-(c[s[i]+2*N]<<20)+s[i];
		else ss[i]=(c[s[i]+2*N]<<20)+s[i];
	}
	for (int i=0; i<2*N; i++)a[abs(ss[i])]=i,upd(i+1); o=-1;
//	for (int i=0; i<2*N; i++)cout<<s[i]<<" ";
	for (int i=0; i<2*N; i++)if(!b[i+1])x=a[abs(ss[i])]+1,b[x]=1,ans+=get(x-1)-get(i)-(ss[i]<0),upd(x);
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:18:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   18 |  for (int i=0; i<2*N; i++)a[abs(ss[i])]=i,upd(i+1); o=-1;
      |  ^~~
shoes.cpp:18:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   18 |  for (int i=0; i<2*N; i++)a[abs(ss[i])]=i,upd(i+1); o=-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