oj.uz

Submission #465994

# Submission time Handle Problem Language Result Execution time Memory
465994 2021-08-17T13:16:01 Z Sench2006 Xor Sort (eJOI20_xorsort) C++14
40 / 100
 66 ms 1048 KB 
#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], b[N];

void solve1() {
    vector <pair<int, int>> ans;
    FOR(i, 1, n + 1) b[i] = a[i];
    FOR(i, 1, n) a[i] ^= a[i + 1], ans.push_back(make_pair(i, i + 1));
    int lastMx = 0;
    FOR(i, 0, n - 1) {
        lastMx = 0;
        FOR(j, 1, n - i + 1) if (b[j] > b[lastMx]) lastMx = j;
        FOR(j, lastMx + 1, n - i + 1) a[j] ^= a[j - 1], ans.push_back(make_pair(j, j - 1)), swap(b[j], b[j - 1]);
        FOR(j, max(lastMx - 1, 1), n - i + 1) a[j] ^= a[j + 1], ans.push_back(make_pair(j, j + 1));
    }    
    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;
}

Compilation message

xorsort.cpp: In function 'void solve1()':
xorsort.cpp:12:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(auto i = a; i < b; i++)
......
   36 |     FOR(i, 0, ans.size()) {
      |         ~~~~~~~~~~~~~~~~                
xorsort.cpp:36:5: note: in expansion of macro 'FOR'
   36 |     FOR(i, 0, ans.size()) {
      |     ^~~
xorsort.cpp: In function 'void solve2()':
xorsort.cpp:12:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(auto i = a; i < b; i++)
......
   56 |     FOR(i, 0, ans.size()) {
      |         ~~~~~~~~~~~~~~~~                
xorsort.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i, 0, ans.size()) {
      |     ^~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 12 ms 588 KB Output is correct
5 Correct 50 ms 872 KB Output is correct
6 Correct 52 ms 800 KB Output is correct
7 Correct 54 ms 884 KB Output is correct
8 Correct 49 ms 804 KB Output is correct
9 Correct 56 ms 840 KB Output is correct
10 Correct 54 ms 912 KB Output is correct
11 Correct 51 ms 836 KB Output is correct
12 Correct 51 ms 900 KB Output is correct
13 Correct 54 ms 912 KB Output is correct
14 Correct 52 ms 896 KB Output is correct
15 Correct 66 ms 1048 KB Output is correct