제출 #133632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133632		ckodser	정렬하기 (IOI15_sorting)	C++14	100 / 100	352 ms	36928 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=6e5+500;
const ll inf=1e9+900;

ll per[maxn];
ll s[maxn];
ll x[maxn];
ll y[maxn];
ll koj[maxn];

void swa(ll a,ll b){
    koj[per[a]]=b;
    koj[per[b]]=a;
    swap(per[a],per[b]);
}	
ll n,m;
vector<pii> vec;

void dfs(ll a){
    if(per[a]==a)return;
    vec.pb(mp(a,per[a]));
    swap(per[a],per[per[a]]);
    dfs(a);
}
void copytoper(){
    for(ll i=0;i<n;i++){
	per[i]=s[i];
    }
}
bool mishe(ll mid){
    copytoper();
    for(ll i=0;i<mid;i++){
	swap(per[x[i]],per[y[i]]);
    }
    vec.clear();
    for(ll i=0;i<n;i++){
	dfs(i);
    }
    return (vec.size()<=mid);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M;
    for(ll i=0;i<n;i++){
	s[i]=S[i];
    }
    for(ll i=0;i<m;i++){
	x[i]=X[i];
	y[i]=Y[i];
    }
    ll b=-1;
    ll e=M;
    while(e-b>1){
	ll mid=(e+b)/2;
	if(mishe(mid)){
	    e=mid;
	}else{
	    b=mid;
	}
    }
    // ans=e;
    copytoper();
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
    }
    vec.clear();
    for(ll i=0;i<n;i++){
	dfs(i);
    }
    while(vec.size()<e){
	vec.pb(mp(0,0));
    }
    if(vec.size()>e){
	return 0;
    }
    for(ll i=0;i<n;i++){
	per[i]=i;
	koj[i]=i;
    }
    for(ll i=e-1;i>=0;i--){
	swa(x[i],y[i]);
    }
    vector<pii> ans;
    for(ll i=0;i<e;i++){
	swa(x[i],y[i]);
	pii a=vec[i];
	ll b1=koj[a.F];
	ll b2=koj[a.S];
	ans.pb(mp(b1,b2));
    }
    for(ll i=0;i<e;i++){
	P[i]=ans[i].F;
	Q[i]=ans[i].S;
    }
    copytoper();
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
	swap(per[Q[i]],per[P[i]]);
    }
    for(ll i=0;i<n;i++){
	if(per[i]!=i){
	    return 0;
	}
    }
    return e;
}

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

sorting.cpp: In function 'bool mishe(int)':
sorting.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return (vec.size()<=mid);
             ~~~~~~~~~~^~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(vec.size()<e){
           ~~~~~~~~~~^~
sorting.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size()>e){
        ~~~~~~~~~~^~

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