Submission #1215516

#TimeUsernameProblemLanguageResultExecution timeMemory
1215516mychecksedadSorting (IOI15_sorting)C++20
100 / 100
234 ms16744 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) { int l = 0, r = m, ans = m; while(l <= r){ int mid = l+r>>1; vector<pii> SW; vector<int> v, pos_val(n), pos_plate(n), plate(n), val(n); for(int i = 1; i <= n; ++i) v.pb(i-1); for(int i = 0; i < n; ++i) val[i] = S[i], pos_val[S[i]] = i; for(int i = 0; i < mid; ++i){ swap(val[X[i]], val[Y[i]]); } for(int i = 0; i < n; ++i){ plate[pos_val[val[i]]] = i; } for(int i = 0; i < n; ++i) val[i] = S[i], pos_val[S[i]] = i; for(int i = 0; i < n; ++i) pos_plate[plate[i]] = i; // cerr << mid << " plate\n"; // for(int x: plate) cerr << x << ' '; // cerr << '\n'; for(int i = 0; i < mid; ++i){ swap(val[X[i]], val[Y[i]]); swap(pos_val[val[X[i]]], pos_val[val[Y[i]]]); swap(plate[X[i]], plate[Y[i]]); swap(pos_plate[plate[X[i]]], pos_plate[plate[Y[i]]]); while(v.size() && pos_plate[v.back()] == pos_val[v.back()]){ v.pop_back(); } if(v.empty()){ SW.pb({0, 0}); // no swap }else{ int vall = v.back(); v.pop_back(); int x = pos_plate[vall]; int y = pos_val[vall]; SW.pb({x, y}); swap(val[x], val[y]); swap(pos_val[val[x]], pos_val[val[y]]); // swap(plate[x], plate[y]); // swap(pos_plate[plate[x]], pos_plate[plate[y]]); } // cerr << "after " << i << '\n'; // for(int x: val) cerr << x << ' '; cerr << '\n'; // for(int x: plate) cerr << x << ' '; cerr << '\n'; // cerr << '\n'; } // cerr << mid << '\n'; // for(int x: plate) cerr << x << ' '; // cerr << '\n'; bool ok = 1; for(int i = 1; i < n; ++i) ok = ok & (val[i] > val[i - 1]); if(ok){ ans = mid; r = mid - 1; for(int i = 0; i < mid; ++i) P[i] = SW[i].ff, Q[i] = SW[i].ss; }else{ l = mid + 1; } } return ans; }
#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...