oj.uz

답안 #775349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775349 2023-07-06T09:55:16 Z Antonn_114 Xor Sort (eJOI20_xorsort) C++14
60 / 100
 7 ms 972 KB 
#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];
                for (auto&j : a){
                    cout << j << " ";
                }
                cout << endl;
            }
        }
    }
    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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 512 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 588 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 4 ms 720 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 512 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 588 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 4 ms 720 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 492 KB Output is correct
18 Correct 3 ms 664 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 4 ms 720 KB Output is correct
21 Correct 3 ms 704 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 3 ms 720 KB Output is correct
24 Correct 3 ms 720 KB Output is correct
25 Correct 3 ms 720 KB Output is correct
26 Correct 7 ms 972 KB Output is correct
27 Correct 6 ms 972 KB Output is correct
28 Correct 7 ms 900 KB Output is correct
29 Correct 6 ms 972 KB Output is correct
30 Correct 6 ms 964 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Integer 780714 violates the range [1, 5]
2 Halted 0 ms 0 KB -