| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 465971 | Sench2006 | Xor Sort (eJOI20_xorsort) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for(auto i = a; i < b; i++)
#define FORD(i, a, b) for(auto i = a - 1; i >= b; i--)
#define trav(x, v) for(auto x : v)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// ---------------------------------------- Solution ---------------------------------------- //
const int N = 1005;
int s, n;
int a[N];
void solve1() {
vector <pair<int, int>> ans;
vector <pair<int, int>> in;
FOR(i, 1, n + 1) {
in.push_back({a[i], i});
}
sort(rall(in));
FOR(j, 0, in.size()) {
int cur = in[j].second;
FOR(i, 1, n) {
a[i] ^= a[i + 1];
ans.push_back(make_pair(i, i + 1));
}
if (i) n--;
FOR(i, cur, n) {
a[i + 1] ^= a[i];
ans.push_back(make_pair(i + 1, i));
}
FORD(i, cur, 0) {
a[i] ^= a[i + 1];
ans.push_back(make_pair(i, i + 1));
}
FOR(i, j + 1, in.size()) {
if (in[i].second > cur) in[i].second--;
}
}
cout << ans.size() << endl;
FOR(i, 0, ans.size()) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
void solve2() {
vector <pair<int, int>> ans;
for(int i = 1; i <= (1 << 20); i *= 2) {
FOR(j, 1, n) {
if((i&a[j])) {
if(!(i&a[j + 1])) {
ans.push_back({j + 1,j});
a[j + 1] ^= a[j];
}
ans.push_back({j, j + 1});
a[j] ^= a[j + 1];
}
}
}
cout << ans.size() << endl;
FOR(i, 0, ans.size()) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
void solve() {
cin >> n >> s;
FOR(i, 1, n + 1) {
cin >> a[i];
}
if (s == 1) solve1();
else solve2();
}
int main() {
fastio;
int tests = 1;
// cin >> tests;
while (tests--) {
solve();
}
return 0;
}