oj.uz

Submission #249009

# Submission time Handle Problem Language Result Execution time Memory
249009 2020-07-14T04:07:58 Z Evirir Sorting (IOI15_sorting) C++17
100 / 100
 494 ms 25932 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 200005;

int findSwapPairs(int n, int A[], int m, int X[], int Y[], int P[], int Q[])
{
	int ans=-1;
	
	bool ok=1;
	for(int i=0;i<n;i++){
		if(A[i]!=i){ ok=0; break; }
	}
	if(ok) return 0;
	
	for(int L=0,R=m-1;L<=R;)
	{		
		int mid=(L+R)>>1;
		if(DEBUG){ cout<<"---------------------------\n"; watch(mid); }
		
		int a[n], loc[n], f[n], floc[n];
		vector<int> p,q;
		for(int i=0;i<n;i++) a[i]=A[i], loc[a[i]]=i, f[i]=i, floc[i]=i;
		for(int i=mid;i>=0;i--){
			int u=X[i], v=Y[i];
			swap(floc[f[u]],floc[f[v]]);
			swap(f[u],f[v]);
			if(DEBUG){
				cout<<"floc: ";
				forn(i,0,n) cout<<floc[i]<<" ";
				cout<<'\n';
			}
		}
		
		int ptr=0;
		for(int i=0;i<=mid;i++){
			int u=X[i], v=Y[i];
			swap(floc[f[u]],floc[f[v]]);
			swap(f[u],f[v]);
			swap(loc[a[u]],loc[a[v]]);
			swap(a[u],a[v]);
			while(ptr<n && loc[ptr]==floc[ptr]) ptr++;
			if(ptr==n){ p.pb(0); q.pb(0); }
			else{
				int tu=loc[ptr], tv=floc[ptr];
				p.pb(tu); q.pb(tv);
				if(DEBUG){
					cout<<"Before:\n";
					watch(ptr); watch(tu); watch(tv);
					cout<<"loc:\t"; forn(i,0,n) cout<<loc[i]<<' '; cout<<'\n';
					cout<<"floc:\t"; forn(i,0,n) cout<<floc[i]<<' '; cout<<'\n';
					cout<<"a:\t"; forn(i,0,n) cout<<a[i]<<' '; cout<<'\n';
					cout<<"\n\n";
				}
				swap(a[tu], a[tv]);
				swap(loc[a[tu]], loc[a[tv]]);
				ptr++;
				if(DEBUG){
					cout<<"After:\n";
					watch(ptr); watch(tu); watch(tv);
					cout<<"loc:\t"; forn(i,0,n) cout<<loc[i]<<' '; cout<<'\n';
					cout<<"floc:\t"; forn(i,0,n) cout<<floc[i]<<' '; cout<<'\n';
					cout<<"a:\t"; forn(i,0,n) cout<<a[i]<<' '; cout<<'\n';
					cout<<"\n\n";
				}
			}
		}
		while(ptr<n && loc[ptr]==floc[ptr]) ptr++;
		if(ptr==n){
			if(DEBUG) cout<<"PASSED\n";
			ans=mid+1;
			for(int i=0;i<=mid;i++) P[i]=p[i], Q[i]=q[i];
			R=mid-1;
		}
		else L=mid+1;
	}
	
	forn(i,0,ans){
		swap(A[X[i]],A[Y[i]]);
		swap(A[P[i]],A[Q[i]]);
	}
	forn(i,1,n){
		if(A[i-1]+1!=A[i]){
			cout<<"FAIL\n"; break;
		}
	}
	
	assert(ans!=-1);
	return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:59:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
     forn(i,0,n) cout<<floc[i]<<" ";
          ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:53:11: note: shadowed declaration is here
   for(int i=mid;i>=0;i--){
           ^
sorting.cpp:79:27: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"loc:\t"; forn(i,0,n) cout<<loc[i]<<' '; cout<<'\n';
                           ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^
sorting.cpp:80:28: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"floc:\t"; forn(i,0,n) cout<<floc[i]<<' '; cout<<'\n';
                            ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^
sorting.cpp:81:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"a:\t"; forn(i,0,n) cout<<a[i]<<' '; cout<<'\n';
                         ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^
sorting.cpp:90:27: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"loc:\t"; forn(i,0,n) cout<<loc[i]<<' '; cout<<'\n';
                           ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^
sorting.cpp:91:28: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"floc:\t"; forn(i,0,n) cout<<floc[i]<<' '; cout<<'\n';
                            ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^
sorting.cpp:92:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
      cout<<"a:\t"; forn(i,0,n) cout<<a[i]<<' '; cout<<'\n';
                         ^
sorting.cpp:11:29: note: in definition of macro 'forn'
 #define forn(i,a,b) for(int i=(a);i<(b);i++)
                             ^
sorting.cpp:65:11: note: shadowed declaration is here
   for(int i=0;i<=mid;i++){
           ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 416 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 316 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 2 ms 640 KB Output is correct
26 Correct 2 ms 640 KB Output is correct
27 Correct 2 ms 640 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 264 ms 23088 KB Output is correct
16 Correct 357 ms 23560 KB Output is correct
17 Correct 494 ms 24600 KB Output is correct
18 Correct 44 ms 13428 KB Output is correct
19 Correct 296 ms 23492 KB Output is correct
20 Correct 338 ms 23980 KB Output is correct
21 Correct 327 ms 23972 KB Output is correct
22 Correct 245 ms 20088 KB Output is correct
23 Correct 278 ms 25672 KB Output is correct
24 Correct 488 ms 25232 KB Output is correct
25 Correct 491 ms 24840 KB Output is correct
26 Correct 326 ms 23984 KB Output is correct
27 Correct 275 ms 23376 KB Output is correct
28 Correct 451 ms 25312 KB Output is correct
29 Correct 433 ms 24824 KB Output is correct
30 Correct 210 ms 22980 KB Output is correct
31 Correct 438 ms 25160 KB Output is correct
32 Correct 297 ms 24724 KB Output is correct
33 Correct 474 ms 25192 KB Output is correct
34 Correct 350 ms 25072 KB Output is correct
35 Correct 302 ms 23048 KB Output is correct
36 Correct 83 ms 22364 KB Output is correct
37 Correct 492 ms 25932 KB Output is correct
38 Correct 453 ms 24968 KB Output is correct
39 Correct 477 ms 25208 KB Output is correct