Submission #774976

#	Time	Username	Problem	Language	Result	Execution time	Memory
774976		CDuong	Xor Sort (eJOI20_xorsort)	C++17	100 / 100	7 ms	1064 KiB

xorsort

/*
pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

int S, n, a[mxN], idx[mxN], maintain[mxN];

void sub2() {
    vii op;
    for(int i = 19; i >= 0; --i) {
        int cnt = 0;
        for(int idx = 1; idx < n; ++idx) {
            int bit1 = (a[idx] >> i & 1);
            int bit2 = (a[idx + 1] >> i & 1);
            if(!bit1) continue;
            if(!bit2) {
                op.emplace_back(idx + 1, idx);
                a[idx + 1] ^= a[idx];
            }
            op.emplace_back(idx, idx + 1);
            a[idx] ^= a[idx + 1], ++cnt;
        }
        if(cnt) --n;
    }
    cout << isz(op) << "\n";
    for(auto tmp : op) cout << tmp.ff << " " << tmp.ss << "\n";
}

void sub1() {
    iota(idx + 1, idx + n + 1, 1);
    iota(maintain + 1, maintain + n + 1, 1);
    sort(idx + 1, idx + n + 1, [&](int x, int y) {
        if(a[x] == a[y]) return x < y;
        return a[x] < a[y];
    });
    
    vii op;
    for(int i = 1; i < n; ++i)
        op.emplace_back(i, i + 1);

    for(int i = n; i > 1; --i) {
        int pos = -1;
        for(int j = 1; j <= i; ++j) {
            if(idx[i] == maintain[j]) {
                pos = j;
                break;
            }
        }
        if(pos == i) {
            op.emplace_back(pos - 1, pos);
            continue;
        }
        for(int j = pos + 1; j <= i; ++j) op.emplace_back(j, j - 1);
        for(int j = max(1, pos - 1); j < i; ++j) op.emplace_back(j, j + 1);
        for(int j = pos; j < i; ++j) swap(maintain[j], maintain[j + 1]);
    }
    
    cout << isz(op) << "\n";
    for(auto tmp : op) cout << tmp.ff << " " << tmp.ss << "\n";
}

void solve() {
    cin >> n >> S;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    if(S == 1) sub1();
    else sub2();
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40