Submission #249009

#TimeUsernameProblemLanguageResultExecution timeMemory
249009EvirirSorting (IOI15_sorting)C++17
100 / 100
494 ms25932 KiB
#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 (stderr)

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++){
           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...