Submission #1005471

#TimeUsernameProblemLanguageResultExecution timeMemory
1005471GrindMachineThe Collection Game (BOI21_swaps)C++17
85 / 100
6 ms840 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 /* read the edi a long time back, remember some key ideas from there */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "swaps.h" int on; vector<vector<int>> bitonic_sort(vector<vector<int>> &curr){ if(curr.empty()) return curr; int siz = sz(curr); vector<vector<int>> res(siz); vector<array<int,3>> cmp; rep(i,siz){ auto &a = curr[i]; if(sz(a) <= 1){ res[i] = a; conts; } rep(x,sz(a)/2){ int y = x+sz(a)/2; if(a[x] > on){ swap(a[x],a[y]); } else if(a[y] > on){ } else{ schedule(a[x],a[y]); cmp.pb({i,x,y}); } } } auto ask = visit(); rep(ind,sz(ask)){ auto [i,x,y] = cmp[ind]; if(!ask[ind]){ swap(curr[i][x],curr[i][y]); } } vector<vector<int>> nxt_bitonic; rep(i,siz){ auto &a = curr[i]; if(sz(a) <= 1) conts; vector<int> b,c; rep(j,sz(a)){ if(j < sz(a)/2){ b.pb(a[j]); } else{ c.pb(a[j]); } } nxt_bitonic.pb(b), nxt_bitonic.pb(c); } nxt_bitonic = bitonic_sort(nxt_bitonic); reverse(all(nxt_bitonic)); rep(i,siz){ auto &a = curr[i]; if(sz(a) <= 1) conts; auto b = nxt_bitonic.back(); nxt_bitonic.pop_back(); auto c = nxt_bitonic.back(); nxt_bitonic.pop_back(); trav(x,c) b.pb(x); res[i] = b; } return res; } vector<vector<int>> sort(vector<vector<int>> &curr){ if(curr.empty()) return curr; int siz = sz(curr); vector<vector<int>> nxt_sort; vector<vector<int>> res(siz); rep(i,siz){ if(sz(curr[i]) <= 1){ res[i] = curr[i]; conts; } vector<int> b,c; rep(j,sz(curr[i])){ if(j < sz(curr[i])/2){ b.pb(curr[i][j]); } else{ c.pb(curr[i][j]); } } nxt_sort.pb(b), nxt_sort.pb(c); } nxt_sort = sort(nxt_sort); reverse(all(nxt_sort)); vector<vector<int>> nxt_bitonic; rep(i,siz){ if(sz(curr[i]) <= 1){ conts; } auto b = nxt_sort.back(); nxt_sort.pop_back(); auto c = nxt_sort.back(); nxt_sort.pop_back(); reverse(all(c)); trav(x,c) b.pb(x); nxt_bitonic.pb(b); } nxt_bitonic = bitonic_sort(nxt_bitonic); reverse(all(nxt_bitonic)); rep(i,siz){ if(sz(curr[i]) <= 1){ conts; } res[i] = nxt_bitonic.back(); nxt_bitonic.pop_back(); } return res; } void solve(int on_, int V) { on = on_; int n = 1; while(n < on) n <<= 1; vector<int> a(n); iota(all(a),1); vector<vector<int>> aa = {a}; auto ans = sort(aa)[0]; while(sz(ans) > on) ans.pop_back(); answer(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...
#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...