#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]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
