Submission #133624

#	Time	Username	Problem	Language	Result	Execution time	Memory
133624		ckodser	Sorting (IOI15_sorting)	C++14	0 / 100	12 ms	760 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=2e5+500;
const ll inf=1e9+900;

ll per[maxn];
ll s[maxn];
ll x[maxn];
ll y[maxn];
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){
    return 0;
    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){
	exit(1);
	cout<<"WTF?!";
	return 0;
    }
    for(ll i=0;i<n;i++){
	per[i]=i;
    }
    for(ll i=e-1;i>=0;i--){
	swap(per[x[i]],per[y[i]]);
    }
    vector<pii> ans;
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
	pii a=vec[i];
	ll b1,b2;
	for(ll i=0;i<n;i++){
	    if(per[i]==a.F)b1=i;
	    if(per[i]==a.S)b2=i;
	}
	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){
	    while(per[i]!=i){
		per[i+1]=i;
	    }
	}
    }
    return e;
}

Compilation message (stderr)

sorting.cpp: In function 'bool mishe(int)':
sorting.cpp:45: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:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(vec.size()<e){
           ~~~~~~~~~~^~
sorting.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size()>e){
        ~~~~~~~~~~^~
sorting.cpp:94:9: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(ll i=0;i<n;i++){
         ^
sorting.cpp:90:12: note: shadowed declaration is here
     for(ll i=0;i<e;i++){
            ^
sorting.cpp:98:11: warning: 'b2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans.pb(mp(b1,b2));
           ^
sorting.cpp:98:11: warning: 'b1' may be used uninitialized in this function [-Wmaybe-uninitialized]

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