Submission #774766

#TimeUsernameProblemLanguageResultExecution timeMemory
774766huutuanXor Sort (eJOI20_xorsort)C++14
40 / 100
5 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]; 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...