oj.uz

Submission #1090103

# Submission time Handle Problem Language Result Execution time Memory
1090103 2024-09-17T17:45:35 Z idk__ Xor Sort (eJOI20_xorsort) C++14
40 / 100
 49 ms 1088 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}), b[i]^=b[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}), b[j+1]^=b[j];
        for(int j = mxi-1; j >=1; j--)op.push_back({j, j-1}), b[j]^=b[j-1];
    
        for(int j=mxi; j<i; j++) swap(b[j], b[j+1]);
    
    }
    // cout << endl;
    // for(auto i : b)cout << i << " ";
    // cout << endl;

}

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:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |    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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 31 ms 980 KB Output is correct
6 Correct 31 ms 980 KB Output is correct
7 Correct 34 ms 980 KB Output is correct
8 Correct 31 ms 980 KB Output is correct
9 Correct 31 ms 992 KB Output is correct
10 Correct 30 ms 992 KB Output is correct
11 Correct 31 ms 1060 KB Output is correct
12 Correct 33 ms 992 KB Output is correct
13 Correct 32 ms 896 KB Output is correct
14 Correct 33 ms 988 KB Output is correct
15 Correct 49 ms 1088 KB Output is correct