oj.uz

답안 #775325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775325 2023-07-06T09:39:55 Z Antonn_114 Xor Sort (eJOI20_xorsort) C++14
60 / 100
 7 ms 984 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){
            bool beau = false;
            for (int i = 19; i >= 0; i--){
                vector<int> ids;
                for (int j = 0; j < n; j++){
                    if ((a[j] >> i) & 1){
                        ids.push_back(j);
                    }
                }
                if (!ids.empty()){
                    if (!beau){
                        for (auto &j : ids){
                            int ptr = j;
                            while(ptr > 0){
                                actions.push_back({ptr - 1, ptr});
                                ptr--;
                            }
                        }
                        int ptr = *ids.rbegin();
                        while(ptr < n - 1){
                            actions.push_back({ptr + 1, ptr});
                            ptr++;
                        }
                        for (int j = 0; j < n - 1; j++){
                            actions.push_back({j, j + 1});
                        }
                        beau = true;
                    }else{
                        for (auto &j : ids){
                            int ptr = j;
                            while(ptr > 0){
                                actions.push_back({ptr - 1, ptr});
                                ptr--;
                            }
                        }
                        int ptr = *ids.rbegin();
                        while(ptr < n - 2){
                            actions.push_back({ptr + 1, ptr});
                            ptr++;
                        }
                    }
                }
            }
            printf("%d\n", int(actions.size()));
            for (auto& i : actions){
                printf("%d %d\n", i.first + 1 ,i.second + 1);
            }
        }
    }
    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 0 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 596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 3 ms 720 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 3 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 0 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 596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 3 ms 720 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 3 ms 720 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 720 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 3 ms 660 KB Output is correct
21 Correct 3 ms 672 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 6 ms 972 KB Output is correct
27 Correct 6 ms 972 KB Output is correct
28 Correct 6 ms 972 KB Output is correct
29 Correct 6 ms 972 KB Output is correct
30 Correct 7 ms 984 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Not sorted
2 Halted 0 ms 0 KB -