제출 #598042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598042		LIF	Arranging Shoes (IOI19_shoes)	C++14	컴파일 에러	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);
}
int 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;
		int x = a[i];
		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;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'int add(int, int)':
shoes.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | }
      | ^
shoes.cpp: In function 'int main()':
shoes.cpp:48:7: warning: unused variable 'x' [-Wunused-variable]
   48 |   int x = a[i];
      |       ^
/usr/bin/ld: /tmp/ccU2BQQk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccectpMl.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccU2BQQk.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