Submission #59176

#	Time	Username	Problem	Language	Result	Execution time	Memory
59176		TadijaSebez	Sorting (IOI15_sorting)	C++11	100 / 100	286 ms	18116 KiB

sorting

#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=200050;
const int M=3*N;
int a[N],b[N],c[N],id[N],qx[M],qy[M];
bool was[N];
int Calc(int n)
{
	int i,j,ret=0;
	for(i=1;i<=n;i++) was[i]=0;
	for(i=1;i<=n;i++)
	{
		if(was[i]) continue;
		ret++;
		for(j=i;!was[j];j=b[j]) was[j]=1;
	}
	return n-ret;
}
void Swap(int &a, int &b){ a^=b;b^=a;a^=b;}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	int n,m,i,j,x,y;
	//scanf("%i",&n);
	n=N;
	for(i=1;i<=n;i++) a[i]=S[i-1]+1;//scanf("%i",&a[i]),a[i]++;
	//scanf("%i",&m);
	m=M;
	for(i=1;i<=m;i++) qx[i]=X[i-1]+1,qy[i]=Y[i-1]+1;//scanf("%i %i",&qx[i],&qy[i]),qx[i]++,qy[i]++;
	int top=m,bot=0,mid,ans=m;
	while(top>=bot)
	{
		mid=top+bot>>1;
		for(i=1;i<=n;i++) b[i]=a[i];
		for(i=1;i<=mid;i++)
		{
			x=qx[i];y=qy[i];
			if(x!=y) Swap(b[x],b[y]);
		}
		//for(i=1;i<=n;i++) printf("%i ",b[i]);printf("\n");
		//printf("%i %i\n",mid,Calc(n));
		if(Calc(n)<=mid) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	//printf("%i\n",ans);
	for(i=1;i<=n;i++) b[i]=c[i]=a[i],id[a[i]]=i,was[i]=0;
	for(i=1;i<=ans;i++)
	{
		x=qx[i];y=qy[i];
		if(x!=y) Swap(b[x],b[y]);
	}
	int k=0;
	vector<pair<int,int> > sol;
	for(i=1;i<=n;i++)
	{
		//for(j=1;j<=n;j++) printf("%i ",b[j]);printf("\n");
		if(b[i]!=i)
		{
			k++;
			x=qx[k];y=qy[k];
			if(x!=y) Swap(id[c[x]],id[c[y]]),Swap(c[x],c[y]);
			//printf("<- %i %i\n",b[i]-1,b[b[i]]-1);
			//printf("%i %i\n",id[b[i]]-1,id[b[b[i]]]-1);
			sol.pb(mp(id[b[i]]-1,id[b[b[i]]]-1));
			Swap(c[id[b[i]]],c[id[b[b[i]]]]);
			Swap(id[b[i]],id[b[b[i]]]);
			int p=b[i];
			Swap(b[i],b[p]);
			i--;
		}
	}
	while(k<ans) sol.pb(mp(0,0)),k++;//printf("0 0\n"),k++;
	for(i=0;i<ans;i++) P[i]=sol[i].first,Q[i]=sol[i].second;
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'void Swap(int&, int&)':
sorting.cpp:22:25: warning: declaration of 'b' shadows a global declaration [-Wshadow]
 void Swap(int &a, int &b){ a^=b;b^=a;a^=b;}
                         ^
sorting.cpp:8:10: note: shadowed declaration is here
 int a[N],b[N],c[N],id[N],qx[M],qy[M];
          ^
sorting.cpp:22:25: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 void Swap(int &a, int &b){ a^=b;b^=a;a^=b;}
                         ^
sorting.cpp:8:5: note: shadowed declaration is here
 int a[N],b[N],c[N],id[N],qx[M],qy[M];
     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:23:76: warning: declaration of 'M' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
                                                                            ^
sorting.cpp:7:11: note: shadowed declaration is here
 const int M=3*N;
           ^
sorting.cpp:23:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
                                                                            ^
sorting.cpp:6:11: note: shadowed declaration is here
 const int N=200050;
           ^
sorting.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
sorting.cpp:25:12: warning: unused variable 'j' [-Wunused-variable]
  int n,m,i,j,x,y;
            ^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26