oj.uz

Submission #775531

# Submission time Handle Problem Language Result Execution time Memory
775531 2023-07-06T13:27:11 Z anhduc2701 Xor Sort (eJOI20_xorsort) C++17
100 / 100
 5 ms 1072 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k;
int a[maxn];
pair<int, int> d[maxn];
vector<pair<int, int>> ans;
void perform(int i, int j)
{
    ans.pb({i, j});
    a[i] ^= a[j];
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i].fi = a[i];
        d[i].se = i;
    }
    sort(d + 1, d + 1 + n);
    int x=n;
    if (k == 1)
    {
        for (int i = 1; i < n; i++)
        {
            perform(i, i + 1);
        }
        for (int i = n; i >=2; i--)
        {
            for (int j = d[i].se; j < i ; j++)
            {
                perform(j+1, j );
            }
            for (int j = d[i].se; j <= i ; j++)
            {
                if (j > 1)
                {
                    perform(j - 1, j);
                }
            }
            for(int j=i-1;j>=1;j--){
                if(d[j].se>d[i].se){
                    d[j].se--;
                }
            }
        }
    }
    else
    {
        for (int i = 19; i >= 0; i--)
        {
            int st0 = 0;
            int st1 = 0;
            vector<int> pos;
            for (int j = 1; j <= n; j++)
            {
                if (BIT(a[j], i) == 1)
                {
                    pos.pb(j);
                }
            }
            int d = 1;
            for (auto v : pos)
            {
                for (int j = v-1; j >=d; j--)
                {
                    perform(j, j + 1);
                }
                d = v + 1;
            }
            if (pos.size())
            {
                for (int j = pos.back(); j < n; j++)
                {
                    perform(j + 1, j);
                }
                for (int j = 1; j < n; j++)
                {
                    perform(j, j + 1);
                }

                n--;
                if(n==0)break;  
            }
        }
    }
    cout << ans.size() << "\n";
    for (auto v : ans)
    {
        cout << v.fi << " " << v.se << "\n";
    }
}

Compilation message

xorsort.cpp: In function 'int main()':
xorsort.cpp:84:17: warning: unused variable 'st0' [-Wunused-variable]
   84 |             int st0 = 0;
      |                 ^~~
xorsort.cpp:85:17: warning: unused variable 'st1' [-Wunused-variable]
   85 |             int st1 = 0;
      |                 ^~~
xorsort.cpp:53:9: warning: unused variable 'x' [-Wunused-variable]
   53 |     int x=n;
      |         ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 596 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 1 ms 340 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 728 KB Output is correct
14 Correct 3 ms 728 KB Output is correct
15 Correct 3 ms 728 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 596 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 1 ms 340 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 728 KB Output is correct
14 Correct 3 ms 728 KB Output is correct
15 Correct 3 ms 728 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 728 KB Output is correct
19 Correct 3 ms 728 KB Output is correct
20 Correct 3 ms 728 KB Output is correct
21 Correct 3 ms 728 KB Output is correct
22 Correct 3 ms 728 KB Output is correct
23 Correct 3 ms 716 KB Output is correct
24 Correct 3 ms 728 KB Output is correct
25 Correct 3 ms 728 KB Output is correct
26 Correct 5 ms 1032 KB Output is correct
27 Correct 5 ms 984 KB Output is correct
28 Correct 5 ms 984 KB Output is correct
29 Correct 5 ms 984 KB Output is correct
30 Correct 5 ms 984 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 844 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 4 ms 980 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 4 ms 980 KB Output is correct
15 Correct 5 ms 1072 KB Output is correct