Submission #152281

#	Time	Username	Problem	Language	Result	Execution time	Memory
152281		tinjyu	정렬하기 (IOI15_sorting)	C++14	74 / 100	73 ms	35164 KiB

sorting

#include "sorting.h"
#include <iostream>
using namespace std;
long long int p[200005],b[200005],n,s[200005],m,x[200005],y[200005],a[200005][2],t;
int check(int sum)
{
	//cout<<sum<<endl;
	for(int i=0;i<n;i++)
	{
		b[s[i]]=i;
		p[i]=s[i];
	}
	for(int i=0;i<sum;i++)
	{
		swap(b[p[x[i]]],b[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		
	}
	
	int tmp=0;
	int tmp2[200005][2],now=-1;
	for(int i=0;i<m;i++)
	{
		tmp2[i][0]=0;
		tmp2[i][1]=0;
	}
	
	for(int i=0;i<n;i++)
	{
		if(b[i]!=i)
		{
			now++;
			tmp++;
			int x1=i,y1=p[i];
			tmp2[now][0]=x1,tmp2[now][1]=y1;
			swap(p[b[i]],p[i]);
			swap(b[x1],b[y1]);
		}
		/*for(int j=0;j<n;j++)cout<<p[j]<<" ";
		cout<<endl;
		for(int j=0;j<n;j++)cout<<b[j]<<" ";
		cout<<endl;
		cout<<endl;*/
	}
	if(tmp<=sum){
		//cout<<endl;
		for(int i=0;i<sum;i++)
		{
			a[i][0]=tmp2[i][0];
			a[i][1]=tmp2[i][1];
		}
		return 1;
	}
	else return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M;
    for(int i=0;i<n;i++)x[i]=X[i];
    for(int i=0;i<n;i++)y[i]=Y[i];
    for(int i=0;i<n;i++)s[i]=S[i];
    int l=0,r=n,ans;
    while(l<=r)
    {
    	int mid=(l+r)/2;
    	//cout<<l<<" "<<r<<" "<<mid<<endl;
    	if(check(mid)==1)
    	{
    		ans=mid;
    		r=mid-1;
		}
		else l=mid+1;
		//system("pause");
	}
	//cout<<ans<<endl;
	for(int i=0;i<n;i++)
	{
		b[s[i]]=i;
		p[i]=s[i];
	}
	for(int i=0;i<ans;i++)
	{
		swap(b[p[x[i]]],b[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
	
		P[i]=b[a[i][0]];
		Q[i]=b[a[i][1]];
		swap(b[p[P[i]]],b[p[Q[i]]]);
		swap(p[P[i]],p[Q[i]]);
	}
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'int check(int)':
sorting.cpp:34:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    int x1=i,y1=p[i];
                ~~~^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int l=0,r=n,ans;
               ^
sorting.cpp:85:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   P[i]=b[a[i][0]];
        ~~~~~~~~~^
sorting.cpp:86:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Q[i]=b[a[i][1]];
        ~~~~~~~~~^
sorting.cpp:61:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int l=0,r=n,ans;
                 ^~~

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