Submission #775351

#	Time	Username	Problem	Language	Result	Execution time	Memory
775351		Antonn_114	Xor Sort (eJOI20_xorsort)	C++14	100 / 100	6 ms	972 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;

// Write down the limits of the problem here

int main() {
    // Try to avoid cin, cout :)

    int tc = 1; // scanf("%d", &tc);
    while(tc--) {
        /// Your solution here
        int n, s;
        scanf("%d%d", &n, &s);
        vector<int> a(n);
        vector<pair<int, int>> actions;

        for (auto&i : a) scanf("%d", &i);
        if (s == 1){
            vector<int> c = a;
            map<int, int> bbb;
            for (int i = 0; i < n; i++){
                bbb[a[i]] = i;
            }
            for (int i = 0; i < n - 1; i++){
                actions.push_back({i, i + 1});
                c[i] ^= c[i + 1];
            }
            int lol = 0;
            for (auto it = bbb.rbegin(); it != bbb.rend(); it++){
                for (int j = it->second; j < n - 1 - lol; j++){
                    actions.push_back({j + 1, j});
                    c[j + 1] ^= c[j];
                    bbb[a[j + 1]]--;
                    a[j] = a[j + 1];
                }
                for (int j = max(it->second - 1, 0); j < n - lol - 1; j++){
                    actions.push_back({j, j + 1});
                    c[j] ^= c[j + 1];
                }
                lol++;
            }
            printf("%d\n", int(actions.size()));
            for (auto &i : actions){
                printf("%d %d\n", i.first + 1, i.second + 1);
            }
        }
        else if (s == 2){
            vector<int> b = a;
            int cnttt = 0;
            for (int i = 19; i >= 0; i--){
                vector<int> ids;
                for (int j = 0; j < n - cnttt; j++){
                    if ((b[j] >> i) & 1){
                        ids.push_back(j);
                    }
                }
                if (!ids.empty()){
                    for (auto &j : ids){
                        int ptr = j;
                        while(ptr > 0 && (((b[ptr - 1] >> i) & 1) ^ 1)){
                            actions.push_back({ptr - 1, ptr});
                            b[ptr - 1] ^= b[ptr];
                            ptr--;
                        }
                    }
                    int ptr = *ids.rbegin();
                    while(ptr < n - 1 && (((b[ptr + 1] >> i) & 1) ^ 1)){
                        b[ptr + 1] ^= b[ptr];
                        actions.push_back({ptr + 1, ptr});
                        ptr++;
                    }
                    for (int j = 0; j < n - 1 - cnttt; j++){
                        actions.push_back({j, j + 1});
                        b[j] ^= b[j + 1];
                    }
                    cnttt++;
                }
            }
            printf("%d\n", int(actions.size()));
            for (auto& i : actions){
                printf("%d %d\n", i.first + 1 ,i.second + 1);
                a[i.first] ^= a[i.second];
            }
        }
    }
    return 0;
}

/*
 * Ermm don't underestimate Div2A, pls...
 * 
 * IMPORTANT:: If there isn't a clear-cut approach for your program, DO NOT CODE YET!
 * 
 * Analyze the time complexity and space complexity even if it *seems* efficient
 *
 * Write down some notes for more complicated problems
 * 
 * Also, please, CP isn't supposed to be complicated
 * 
 **/

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d%d", &n, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~
xorsort.cpp:17:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         for (auto&i : a) scanf("%d", &i);
      |                          ~~~~~^~~~~~~~~~

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