oj.uz

Submission #460752

# Submission time Handle Problem Language Result Execution time Memory
460752 2021-08-09T09:09:27 Z Tenis0206 Xor Sort (eJOI20_xorsort) C++11
100 / 100
 8 ms 1032 KB 
#include <bits/stdc++.h>

using namespace std;
int n,s,v[100005],aux[100005];
bool get_bit(int val, int b)
{
    return ((val&(1<<b))!=0);
}
void debug(int *a)
{
    for(int i=1;i<=n;i++)
    {
        cerr<<a[i]<<' ';
    }
    cerr<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    if(s==1)
    {
        vector<pair<int,int>> rez;
        for(int i=1;i<=n;i++)
        {
            aux[i] = v[i];
        }
        for(int i=1;i<n;i++)
        {
            int poz = 0;
            for(int j=1;j<=n-i+1;j++)
            {
                if(aux[j]>aux[poz])
                {
                    poz = j;
                }
            }
            for(int j=1;j<=n-i;j++)
            {
                v[j]^=v[j+1];
                rez.push_back({j,j+1});
            }
            int x = aux[poz];
            for(int j=poz;j<n-i+1;j++)
            {
                aux[j] = aux[j+1];
            }
            aux[n-i+1] = x;
            for(int j=poz+1;j<=n-i+1;j++)
            {
                v[j]^=v[j-1];
                rez.push_back({j,j-1});
            }
            for(int j=poz-2;j>=1;j--)
            {
                v[j]^=v[j+1];
                rez.push_back({j,j+1});
            }
        }
        for(int i=n-1;i>=1;i--)
        {
            v[i]^=v[i+1];
            rez.push_back({i,i+1});
        }
        cout<<rez.size()<<'\n';
        for(auto it : rez)
        {
            cout<<it.first<<' '<<it.second<<'\n';
        }
        return 0;
    }
    vector<pair<int,int>> rez;
    for(int b=0; b<20; b++)
    {
        for(int i=2; i<=n; i++)
        {
            if(get_bit(v[i-1],b)==0)
            {
                continue;
            }
            if(get_bit(v[i],b)==1 && get_bit(v[i-1],b)==1)
            {
                rez.push_back({i-1,i});
                v[i-1]^=v[i];
                continue;
            }
            if(get_bit(v[i],b)==0 && get_bit(v[i-1],b)==1)
            {
                rez.push_back({i,i-1});
                v[i]^=v[i-1];
                rez.push_back({i-1,i});
                v[i-1]^=v[i];
            }
        }
    }
    cout<<rez.size()<<'\n';
    for(auto it : rez)
    {
        cout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 712 KB Output is correct
5 Correct 5 ms 720 KB Output is correct
6 Correct 5 ms 720 KB Output is correct
7 Correct 5 ms 720 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 5 ms 720 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 5 ms 720 KB Output is correct
12 Correct 5 ms 720 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 5 ms 720 KB Output is correct
15 Correct 5 ms 708 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 712 KB Output is correct
5 Correct 5 ms 720 KB Output is correct
6 Correct 5 ms 720 KB Output is correct
7 Correct 5 ms 720 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 5 ms 720 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 5 ms 720 KB Output is correct
12 Correct 5 ms 720 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 5 ms 720 KB Output is correct
15 Correct 5 ms 708 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 720 KB Output is correct
18 Correct 8 ms 976 KB Output is correct
19 Correct 8 ms 1028 KB Output is correct
20 Correct 8 ms 976 KB Output is correct
21 Correct 8 ms 976 KB Output is correct
22 Correct 8 ms 928 KB Output is correct
23 Correct 8 ms 976 KB Output is correct
24 Correct 8 ms 1032 KB Output is correct
25 Correct 8 ms 976 KB Output is correct
26 Correct 8 ms 976 KB Output is correct
27 Correct 8 ms 968 KB Output is correct
28 Correct 8 ms 976 KB Output is correct
29 Correct 8 ms 968 KB Output is correct
30 Correct 8 ms 976 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 6 ms 848 KB Output is correct
6 Correct 7 ms 936 KB Output is correct
7 Correct 6 ms 844 KB Output is correct
8 Correct 6 ms 848 KB Output is correct
9 Correct 6 ms 848 KB Output is correct
10 Correct 6 ms 848 KB Output is correct
11 Correct 7 ms 848 KB Output is correct
12 Correct 6 ms 848 KB Output is correct
13 Correct 6 ms 848 KB Output is correct
14 Correct 7 ms 848 KB Output is correct
15 Correct 8 ms 976 KB Output is correct