제출 #421320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421320		errorgorn	정렬하기 (IOI15_sorting)	C++17	100 / 100	327 ms	37092 KiB

sorting

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "sorting.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());


int n,m;
vector<int> s,arr;
vector<ii> sw;

vector<ii> changes;
bool vis[200005];

int can(int i){
	changes.clear();
	memset(vis,false,sizeof(vis));
	arr=s;
	
	rep(x,0,i){
		swap(arr[sw[x].fi],arr[sw[x].se]);
	}
	
	//cout<<i<<": "; rep(x,0,n) cout<<arr[x]<<" "; cout<<endl;
	
	rep(x,0,n) if (!vis[x]){
		int curr=x;
		vector<int> v;
		
		do{
			vis[curr]=true;
			v.pub(curr);
			curr=arr[curr];
		} while (curr!=x);
		
		rep(x,0,sz(v)-1) changes.pub(ii(v[x],v[x+1]));
	}
	
	//cout<<i<<" "<<sz(changes)<<endl;
	return sz(changes);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M;
    rep(x,0,n) s.pub(S[x]);
    rep(x,0,m) sw.pub(ii(X[x],Y[x]));
    
    int lo=-1,hi=m,mi;
    while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (can(mi)<=mi) hi=mi;
		else lo=mi;
	}
	
	can(hi);
	
	//cout<<hi<<endl;
	//for (auto &it:changes) cout<<it.fi<<" "<<it.se<<endl;
    
    vector<int> idx,pos;
    rep(x,0,n) idx.pub(x),pos.pub(x);
    
    rep(x,hi,0){
		swap(pos[idx[sw[x].fi]],pos[idx[sw[x].se]]);
		swap(idx[sw[x].fi],idx[sw[x].se]);
	}
	
	rep(x,0,hi){
		swap(pos[idx[sw[x].fi]],pos[idx[sw[x].se]]);
		swap(idx[sw[x].fi],idx[sw[x].se]);
		
		if (!changes.empty()){
			P[x]=pos[changes.back().fi];
			Q[x]=pos[changes.back().se];
			changes.pob();
		}
		else{
			P[x]=0;
			Q[x]=0;
		}
	}
    
    return hi;
}

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

sorting.cpp: In function 'int can(int)':
sorting.cpp:66:7: warning: declaration of 'x' shadows a previous local [-Wshadow]
   66 |   rep(x,0,sz(v)-1) changes.pub(ii(v[x],v[x+1]));
      |       ^
sorting.cpp:28:35: note: in definition of macro 'rep'
   28 | #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
      |                                   ^
sorting.cpp:56:6: note: shadowed declaration is here
   56 |  rep(x,0,n) if (!vis[x]){
      |      ^
sorting.cpp:28:35: note: in definition of macro 'rep'
   28 | #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
      |                                   ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:80:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   mi=hi+lo>>1;
      |      ~~^~~

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