oj.uz

Submission #1090091

# Submission time Handle Problem Language Result Execution time Memory
1090091 2024-09-17T17:28:18 Z idk__ Xor Sort (eJOI20_xorsort) C++14
40 / 100
 47 ms 1048 KB 
#include <bits/stdc++.h>
using namespace std;
int a[1001], n, s;
vector<pair<int, int>>op;
void s1(){
    for(int i = 0;i < n-1; i++)op.push_back({i, i+1});

    for(int i = n-1; i>=0; i--){
        int mxi = 0;
        for(int j = 0;j <= i; j++)if(a[j] > a[mxi])mxi = j;
        for(int j = mxi; j < i; j++)op.push_back({j+1, j});
        for(int j = mxi; j >=1; j--)op.push_back({j, j-1});
    
        for(int j=mxi; j<i; j++) swap(a[j], a[j+1]);
    
    }

}

void s2(){
    for(int i = 19; i>=0; i--){

        for(int j = 0;j < n-1; j++){
            
            int bt = (1 << i);

            if(a[j+1] >= (1<<(i+1)))break;
            //1, 0, C=1
            //0, 1
            //1, 1, c = 2
            //0, 0
            if((bt&a[j]) and !(bt&a[j+1]))op.push_back({j+1, j}), a[j+1]^=a[j];
            if((bt&a[j]) and (bt&a[j+1]))op.push_back({j, j+1}), a[j]^=a[j+1];
            

        }
       
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    for(int i = 0;i < n; i++)cin >> a[i];

    if(s==1)s1();
    else s2();

    cout << op.size() << endl;
   for(auto [i, j] : op)cout << i+1 << " " << j+1 << endl;
    
  // for(int i = 0;i < n; i++)cout << a[i] << " ";

    
    
    }

Compilation message

xorsort.cpp: In function 'int main()':
xorsort.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |    for(auto [i, j] : op)cout << i+1 << " " << j+1 << endl;
      |             ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# 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 2 ms 344 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 30 ms 992 KB Output is correct
6 Correct 47 ms 984 KB Output is correct
7 Correct 31 ms 988 KB Output is correct
8 Correct 31 ms 992 KB Output is correct
9 Correct 30 ms 988 KB Output is correct
10 Correct 31 ms 992 KB Output is correct
11 Correct 32 ms 992 KB Output is correct
12 Correct 33 ms 1004 KB Output is correct
13 Correct 32 ms 1048 KB Output is correct
14 Correct 34 ms 992 KB Output is correct
15 Correct 41 ms 992 KB Output is correct