oj.uz

답안 #1076871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1076871 2024-08-26T17:33:28 Z horiaboeriu Xor Sort (eJOI20_xorsort) C++17
100 / 100
 8 ms 948 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 1000
#define MAX 40000
#define MAXB 19
int v[MAXN], rez1[MAX], rez2[MAX];
int nr;
void calcxor(int i, int j) {
    rez1[nr] = i + 1;
    rez2[nr] = j + 1;
    //in i se face xorul celor doua
    nr++;
}
int main()
{
    int n, s, i, k, ul, x, p, b;
    scanf("%d%d", &n, &s);
    for (i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    if (s == 1) {
        //o sa fac o sortare prin selectie care va avea n * (n - 1) / 2 * 2 operatii care este fix sub 40000
        for (i = 0; i < n - 1; i++) {
            calcxor(i, i + 1);
        }
        for (ul = n - 1; ul > 0; ul--) {
            //caut maximul
            k = 0;
            for (i = 1; i <= ul; i++) {
                if (v[i] > v[k]) {
                    k = i;
                }
            }
            //acum pe fiecare poz ar fi v[poz] ^ v[poz + 1], iar pe ultima poz este v[ul]
            for (i = k + 1; i <= ul; i++) {
                calcxor(i, i - 1);
            }
            //acum in pozitiile <= k este v[poz] ^ v[poz + 1] si pe poz, (k < poz < ul) este v[k] ^ v[poz + 1] ca celelalte apar de un numar par de ori si se elimina
            //si pe ultima poz, adica pozitia ul este v[k]

            if (k > 0) {
                calcxor(k - 1, k);
            }
            for (i = k; i < ul; i++) {
                calcxor(i, i + 1);
            }
            //acum in pe fiecare pozitie < k - 1 este v[poz] ^ v[poz + 1], pe poz k - 1 este v[k - 1] ^ v[k + 1]
            //si pe fiecare poz, k < poz < ul - 1 este v[poz + 1] ^ v[poz + 2], pe ul - 1 este v[ul] si pe ul este v[k]
            x = v[k];
            for (i = k + 1; i <= ul; i++) {
                v[i - 1] = v[i];
            }
            v[ul] = x;
            //acum, pentru ca am shiftat la stanga tot de la k, pe fiecare poz este v[poz] ^ v[poz + 1] si pe ul - 1 este v[ul]
            //in v fiind numerele originale
        }
    } else {
        p = (1 << MAXB);
        for (b = MAXB; b >= 0; b--) {
            //daca apare bitul b la orice numar o sa il fac sa apara doar la ultimul
            for (i = 0; i < n - 1; i++) {
                if ((v[i] & p) > 0) {
                    if ((v[i + 1] & p) == 0) {
                       //apare doar in primul deci il pun si in al doilea
                        calcxor(i + 1, i);
                        v[i + 1] ^= v[i];
                    }
                    //apare in ambele deci il scot din primul
                    calcxor(i, i + 1);
                    v[i] ^= v[i + 1];
                }
            }
            if (n > 0 && (v[n - 1] & p) > 0) {
                n--;//acesta este sigur mai mare ca restul
            }
            p /= 2;
        }
        //primele numere vor fi 0
    }
    printf("%d\n", nr);
    for (i = 0; i < nr; i++) {
        printf("%d %d\n", rez1[i], rez2[i]);
    }
    return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 372 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 600 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 372 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 732 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 4 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 8 ms 860 KB Output is correct
27 Correct 7 ms 948 KB Output is correct
28 Correct 7 ms 860 KB Output is correct
29 Correct 8 ms 860 KB Output is correct
30 Correct 7 ms 920 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 704 KB Output is correct
12 Correct 6 ms 856 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 4 ms 860 KB Output is correct