Submission #774807

#TimeUsernameProblemLanguageResultExecution timeMemory
774807huutuanXor Sort (eJOI20_xorsort)C++14
40 / 100
6 ms1492 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) ((int)x.size()) #define sumof(x) accumulate(all(x), 0ll) const int N=1001; int n, s, a[N]; void solve(int tc){ // cout << "Case #" << tc << ": "; vector<pair<int, int>> v; cin >> n >> s; for (int i=1; i<=n; ++i) cin >> a[i]; function<void(int, int)> bubble_sort=[&](int l, int r) -> void { while (1){ bool stop=true; for (int i=l; i<r; ++i) if (a[i]>a[i+1]){ swap(a[i], a[i+1]); stop=false; v.emplace_back(i, i+1); v.emplace_back(i+1, i); v.emplace_back(i, i+1); } if (stop) break; } }; if (s==1){ for (int i=19; i>=0; --i){ vector<int> idx; for (int j=1; j<=n; ++j) if (a[j]>>i&1) idx.push_back(j); if (idx.empty()) continue; int max_cnt=(1<<i)-1; int bit0=min(max_cnt, n-1); for (int j=1; j<=bit0; ++j) if (a[j]>>i&1){ if (!(a[j+1]>>i&1)){ v.emplace_back(j+1, j); a[j+1]^=a[j]; } v.emplace_back(j, j+1); a[j]^=a[j+1]; } for (int j=bit0+1; j<=n; ++j) if (a[j]>>i&1){ int idx1=j, idx2=j; while (idx1>bit0+1 && !(a[idx1-1]>>i&1)) --idx1; while (idx2<n && !(a[idx2+1]>>i&1)) ++idx2; for (int k=j-1; k>=idx1; --k){ v.emplace_back(k, k+1); a[k]^=a[k+1]; } for (int k=j+1; k<=idx2; ++k){ v.emplace_back(k, k-1); a[k]^=a[k-1]; } } bubble_sort(bit0+1, n); n=bit0; } }else{ for (int i=19; i>=0; --i){ vector<int> idx; for (int j=1; j<=n; ++j) if (a[j]>>i&1) idx.push_back(j); if (idx.empty()) continue; for (int j=1; j<sz(idx); ++j){ int i1=idx[j-1], i2=idx[j]; for (int k=i1; k<i2-1; ++k){ v.emplace_back(k+1, k); a[k+1]^=a[k]; v.emplace_back(k, k+1); a[k]^=a[k+1]; } v.emplace_back(i2-1, i2); a[i2-1]^=a[i2]; } if (idx.back()!=n){ for (int j=idx.back(); j<n; ++j){ v.emplace_back(j+1, j); a[j+1]^=a[j]; v.emplace_back(j, j+1); a[j]^=a[j+1]; } } --n; } } cout << sz(v) << '\n'; for (auto& i:v) cout << i.first << ' ' << i.second << '\n'; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int ntests=1; // cin >> ntests; for (int i=1; i<=ntests; ++i) solve(i); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...