제출 #152468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152468		tinjyu	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	3 ms	1916 KiB

shoes

#include "shoes.h"
#include <iostream>
using namespace std;
long long int tag[1000005],l,r,n,tree[1000005],map[1000005],road[1000005];
long long int change(int s,int e,int t)
{
	if(l<s || l>e)return tree[t];
	if(s==e)return tree[t]=1;
	return tree[t]=change(s,(s+e)/2,t*2)+change((s+e)/2+1,e,t*2+1);
}
long long int find(int s,int e,int t)
{
	if(l>e || r<s)return 0;
	if(l<=s && e<=r)return tree[t];
	return find(s,(s+e)/2,t*2)+find((s+e)/2+1,e,t*2+1);
}
long long count_swaps(std::vector<int> s) {
	freopen("a.out","w",stdout);
	n=s.size();
	n/=2;
	for(int i=0;i<=200000;i++)road[i]=-1;
	for(int i=2*n-1;i>=0;i--)
	{
		if(s[i]<0)
		{
			s[i]*=-1;
			s[i]+=100000;
		}
		map[i]=road[s[i]];
		road[s[i]]=i;
	}
	long long int ans=0;
	for(int i=0;i<2*n-1;i++)
	{
		if(tag[i]==1)continue;
		int st=road[s[i]];
		if(s[i]<=100000)ans++;
		tag[st]=1;
		road[s[i]]=map[road[s[i]]];
		int x=(s[i]+100000)%200000;
		int p=road[x];
		tag[p]=1;
		l=p;
		if(i>=80000)cout<<st<<" "<<p<<endl;
		road[x]=map[road[x]];
		change(0,2*n-1,1);
		ans+=p-st-1;
		l=st+1;
		r=p-1;
		
		long long int tmp=find(0,2*n-1,1);
		ans-=tmp;
		if(i>=80000)
		{
			cout<<ans<<" "<<tmp<<" "<<(199999+p-st)*(i-1)/2<<endl;
		}
		if(ans!=(199999+p-st)*i/2)
		{
			cout<<"worng"<<endl;
		}
	}
	return ans;
}

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("a.out","w",stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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