#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];
}
}
}
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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 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 |
3 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 |
4 ms |
720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 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 |
3 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 |
4 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 |
720 KB |
Output is correct |
| 21 |
Correct |
3 ms |
720 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 |
668 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 |
6 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
4 ms |
808 KB |
Output is correct |
| 6 |
Correct |
5 ms |
844 KB |
Output is correct |
| 7 |
Correct |
4 ms |
844 KB |
Output is correct |
| 8 |
Correct |
4 ms |
844 KB |
Output is correct |
| 9 |
Correct |
4 ms |
844 KB |
Output is correct |
| 10 |
Correct |
5 ms |
812 KB |
Output is correct |
| 11 |
Correct |
5 ms |
844 KB |
Output is correct |
| 12 |
Correct |
5 ms |
844 KB |
Output is correct |
| 13 |
Correct |
5 ms |
844 KB |
Output is correct |
| 14 |
Correct |
5 ms |
844 KB |
Output is correct |
| 15 |
Correct |
5 ms |
972 KB |
Output is correct |
