oj.uz

Submission #1090082

# Submission time Handle Problem Language Result Execution time Memory
1090082 2024-09-17T17:19:53 Z idk__ Xor Sort (eJOI20_xorsort) C++14
40 / 100
 59 ms 992 KB 
#include <bits/stdc++.h>
using namespace std;
int a[1001], n, s;
vector<pair<int, int>>op;
void s1(){
    int b[n]={};
    for(int i = 0;i < n; i++)b[i] = a[i];
    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(b[j] > b[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});
    }

}

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];
            

        }
       //for(int j = 0;j < n; j++)cout << a[j] << " ";
        //cout <<endl;
    }
}

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:14: 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 0 ms 348 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 3 ms 348 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 31 ms 944 KB Output is correct
6 Correct 31 ms 992 KB Output is correct
7 Correct 31 ms 968 KB Output is correct
8 Correct 32 ms 900 KB Output is correct
9 Correct 31 ms 912 KB Output is correct
10 Correct 31 ms 988 KB Output is correct
11 Correct 36 ms 992 KB Output is correct
12 Correct 34 ms 992 KB Output is correct
13 Correct 39 ms 992 KB Output is correct
14 Correct 34 ms 912 KB Output is correct
15 Correct 59 ms 988 KB Output is correct