제출 #967602

#제출 시각아이디문제언어결과실행 시간메모리
967602GrindMachine정렬하기 (IOI15_sorting)C++17
100 / 100
292 ms19404 KiB
#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; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: edi if we can check if ans <= mid, then we can run a b.s how to check if ans <= mid? key idea: look at both players' swaps separately bob swaps plates, alice swaps apples goal: apple i belongs to plate i plates initially 0,1,...,n-1 apples initially a[0],a[1],...,a[n-1] because both guys operate individually, one can do all ops before the other (inter order doesnt matter) apples = 4 3 2 1 0 plates = 0 1 2 3 4 plates (0,1): apples = 4 3 2 1 0 plates = 1 0 2 3 4 plates (1,2): apples = 4 3 2 1 0 plates = 2 0 1 3 4 plates (2,3): apples = 4 3 2 1 0 plates = 3 0 1 2 4 now consider alice's swaps alice only swaps apples the final arrangement of plates is already decided apple i needs to go on plate i create a functional graph from each apple to its respective final position in the eg above, 4 --> 0 --> 3 (apple 4 needs to go to apple 0's position etc) and 1 --> 2 ans <= mid if sz(to_swap) <= mid (sz(to_swap) = 3), which is true in this case after each swap of bob, alice swaps one pair of apples apples (0,3): apples = 4 0 2 1 3 plates = 3 0 1 2 4 apples (3,4): apples = 3 0 2 1 4 plates = 3 0 1 2 4 apples (1,2): apples = 3 0 1 2 4 plates = 3 0 1 2 4 need some care when writing to arrays P[] and Q[] because we need to fill indices (i.e plates), not apples can be done on the go by maintaining the order of plates, positions of plates, order of apples and positions of apples on the go */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "sorting.h" int findSwapPairs(int n, int a[], int m, int X[], int Y[], int P[], int Q[]) { if(is_sorted(a,a+n)) return 0; auto ok = [&](int mid, int t){ vector<int> plates(n), plate_pos(n); iota(all(plates),0), iota(all(plate_pos),0); rep(i,mid){ // swap plates x and y int x = X[i], y = Y[i]; int &p = plate_pos[x], &q = plate_pos[y]; swap(plates[p],plates[q]); swap(p,q); } vector<bool> vis(n); vector<pii> to_swap; // pairs of apples that need to be swapped rep(i,n){ if(vis[i]) conts; int j = i; vector<int> apples; while(!vis[j]){ vis[j] = 1; apples.pb(a[j]); j = plate_pos[a[j]]; } rep(k,sz(apples)-1){ to_swap.pb({apples[k],apples.back()}); } } if(!t){ return sz(to_swap) <= mid; } iota(all(plates),0), iota(all(plate_pos),0); vector<int> apples(n), apple_pos(n); rep(i,n) apples[i] = a[i], apple_pos[a[i]] = i; rep(i,mid){ { int x = X[i], y = Y[i]; int &p = plate_pos[x], &q = plate_pos[y]; swap(plates[p],plates[q]); swap(p,q); } if(!to_swap.empty()){ auto [x,y] = to_swap.back(); to_swap.pop_back(); int &p = apple_pos[x], &q = apple_pos[y]; P[i] = plates[p], Q[i] = plates[q]; swap(apples[p],apples[q]); swap(p,q); } } rep(i,n) assert(plates[i] == apples[i]); return true; }; int l = 1, r = m; int ans = -1; while(l <= r){ int mid = (l+r) >> 1; if(ok(mid,0)){ ans = mid; r = mid-1; } else{ l = mid+1; } } ok(ans,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...