제출 #152273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152273		tinjyu	Sorting (IOI15_sorting)	C++14	20 / 100	3 ms	508 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]=b[i],tmp2[now][1]=i;
			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){
		for(int i=0;i<sum;i++)
		{
			a[i][0]=tmp2[i][0];
			a[i][1]=tmp2[i][1];
			//cout<<a[i][0]<<" "<<a[i][1]<<endl;
		}
		//cout<<endl;
		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;
	}
	//cout<<ans<<endl;
	for(int i=0;i<ans;i++)
	{
		P[i]=a[i][0];
		Q[i]=a[i][1];
	}
	return ans;
}

컴파일 시 표준 에러 (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:35:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    tmp2[now][0]=b[i],tmp2[now][1]=i;
                 ~~~^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:62:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int l=0,r=n,ans;
               ^
sorting.cpp:77:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   P[i]=a[i][0];
        ~~~~~~^
sorting.cpp:78:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Q[i]=a[i][1];
        ~~~~~~^
sorting.cpp:62: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: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26