Submission #598045

#	Time	Username	Problem	Language	Result	Execution time	Memory
598045		LIF	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n;
int a[200005];
vector<int> v[300005];
long long int sum[300005];
bool vis[300005];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int val)
{
	while(x<=n)
	{
		sum[x] +=val;
		x+=lowbit(x);
	}
}
long long int getsum(int x)
{
	long long int ans = 0;
	while(x>0)
	{
		ans += sum[x];
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
	cin>>n;
	n<<=1;
	for(int i=1;i<=n;i++)
	{
		vis[i] = false;
		cin>>a[i];
		int x = a[i];
		v[x+n].push_back(i);
		add(i,1);
	}
	long long int ans = 0;
	for(int i=n;i>=1;i--)//from the last to begin."Reserve".
	{
		if(vis[i] == true)continue;
		vis[i] = true;
		v[a[i]+n].pop_back();
		int res  = v[n-a[i]].back();
		v[n-a[i]].pop_back();
		vis[res] = true;
		ans = ans + getsum(i-1)-getsum(res); //we only need to push the "res" to i-1.
		if(a[i]<0) //since we collect pair in every time, we only need to observe the odd. if the odd is <0,that means it should swap one more time.
		{
			ans+=1;
		}
		add(res,-1);
	}
	//Although we haven't do one time in really life, we have try it in the brain.
	cout<<ans<<endl;
	
	
	
	
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccWQgelP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyNt8VL.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccWQgelP.o: in function `main':
grader.cpp:(.text.startup+0x29d): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status