Submission #775532

#	Time	Username	Problem	Language	Result	Execution time	Memory
775532		vjudge1	Xor Sort (eJOI20_xorsort)	C++17	100 / 100	5 ms	1088 KiB

xorsort

/*
#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 (stderr)

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 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40