Submission #1076845

#TimeUsernameProblemLanguageResultExecution timeMemory
1076845horiaboeriuXor Sort (eJOI20_xorsort)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 1000 #define MAX 40000 int v[MAXN], rez1[MAX], rez2[MAX]; int nr; void calcxor(int i, int j) { rez1[nr] = i; rez2[nr] = j; //in i se face xorul celor doua nr++; } int main() { int n, s, i, k, ul, x; 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 { } printf("%d\n", nr); for (i = 0; i < nr; i++) { printf("%d %d\n", rez1[i], rez2[i]); } return 0; }

Compilation message (stderr)

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