oj.uz

Submission #421320

# Submission time Handle Problem Language Result Execution time Memory
421320 2021-06-09T02:42:13 Z errorgorn Sorting (IOI15_sorting) C++17
100 / 100
 327 ms 37092 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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;
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 432 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 1096 KB Output is correct
22 Correct 2 ms 968 KB Output is correct
23 Correct 2 ms 1096 KB Output is correct
24 Correct 2 ms 1088 KB Output is correct
25 Correct 2 ms 1096 KB Output is correct
26 Correct 2 ms 1096 KB Output is correct
27 Correct 2 ms 968 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 836 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 832 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 828 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 2 ms 832 KB Output is correct
14 Correct 2 ms 844 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 836 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 832 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 828 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 2 ms 832 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 218 ms 34136 KB Output is correct
16 Correct 231 ms 34832 KB Output is correct
17 Correct 251 ms 36496 KB Output is correct
18 Correct 192 ms 30940 KB Output is correct
19 Correct 281 ms 35028 KB Output is correct
20 Correct 327 ms 35148 KB Output is correct
21 Correct 283 ms 35412 KB Output is correct
22 Correct 222 ms 31256 KB Output is correct
23 Correct 241 ms 37092 KB Output is correct
24 Correct 253 ms 36624 KB Output is correct
25 Correct 260 ms 36364 KB Output is correct
26 Correct 286 ms 32688 KB Output is correct
27 Correct 270 ms 31576 KB Output is correct
28 Correct 276 ms 36820 KB Output is correct
29 Correct 305 ms 34936 KB Output is correct
30 Correct 277 ms 31736 KB Output is correct
31 Correct 294 ms 35708 KB Output is correct
32 Correct 244 ms 36536 KB Output is correct
33 Correct 252 ms 36644 KB Output is correct
34 Correct 245 ms 36112 KB Output is correct
35 Correct 281 ms 34260 KB Output is correct
36 Correct 187 ms 31660 KB Output is correct
37 Correct 298 ms 37008 KB Output is correct
38 Correct 276 ms 35916 KB Output is correct
39 Correct 255 ms 35936 KB Output is correct