oj.uz

Submission #774976

# Submission time Handle Problem Language Result Execution time Memory
774976 2023-07-06T06:25:13 Z CDuong Xor Sort (eJOI20_xorsort) C++17
100 / 100
 7 ms 1064 KB 
/*
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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 716 KB Output is correct
14 Correct 3 ms 728 KB Output is correct
15 Correct 3 ms 724 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 716 KB Output is correct
14 Correct 3 ms 728 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 728 KB Output is correct
19 Correct 4 ms 728 KB Output is correct
20 Correct 4 ms 728 KB Output is correct
21 Correct 3 ms 728 KB Output is correct
22 Correct 3 ms 740 KB Output is correct
23 Correct 4 ms 728 KB Output is correct
24 Correct 3 ms 720 KB Output is correct
25 Correct 4 ms 728 KB Output is correct
26 Correct 7 ms 1028 KB Output is correct
27 Correct 7 ms 984 KB Output is correct
28 Correct 7 ms 984 KB Output is correct
29 Correct 5 ms 984 KB Output is correct
30 Correct 5 ms 984 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 4 ms 952 KB Output is correct
8 Correct 4 ms 836 KB Output is correct
9 Correct 6 ms 856 KB Output is correct
10 Correct 4 ms 844 KB Output is correct
11 Correct 4 ms 848 KB Output is correct
12 Correct 4 ms 984 KB Output is correct
13 Correct 6 ms 972 KB Output is correct
14 Correct 4 ms 856 KB Output is correct
15 Correct 5 ms 1064 KB Output is correct