QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111279#1899. Maximaze XOR sumanhduc2701WA 2ms3580kbC++232.3kb2023-06-06 16:25:272023-06-06 16:25:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-06 16:25:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3580kb
  • [2023-06-06 16:25:27]
  • 提交

answer

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
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::steady_clock::now().time_since_epoch().count());
int n;
int a[maxn];
int b[maxn];
int xo[60];
int p[60];
int q[60];
int s = 0;
int d = 0;
bool add(int x, int id)
{
    int su = 0;
    for (int i = 59; i >= 0; i--)
    {
        if ((((1LL << i) & x) == 0) || (((1LL << i) & d)))
            continue;
        if (p[i] == 0)
        {
            p[i] = x;
            su ^= (1LL << i);
            xo[i] = su;
            q[i] = id;
            return true;
        }
        else
        {
            x ^= p[i];
            su ^= xo[i];
        }
    }
    return false;
}
pair<int, int> check(int x)
{
    int so = 0;
    for (int i = 59; i >= 0; i--)
    {
        if ((p[i] == 0) || ((1LL << i) & x))
            continue;

        x ^= p[i];
        so ^= xo[i];
    }

    return {x, so};
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s ^= a[i];
        d ^= a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];

        d ^= b[i];
        b[i] ^= a[i];
        add(b[i], i);
    }
    pair<int, int> ans = check(s);
    cout << ((d ^ ans.fi) + (ans.fi)) << " ";
    int p = ans.se;
    cout << __builtin_popcount(ans.se) << "\n";
    for (int i = 59; i >= 0; i--)
    {
        if ((1LL << i) & p)
        {
            cout << q[i] << " ";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3580kb

input:

2
1 1
2 2

output:

6 1
2 

result:

ok n=2

Test #2:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

10
12 0 4 3 1 1 12 3 11 11
3 3 14 6 14 15 1 15 5 2

output:

26 1
1 

result:

ok n=10

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3448kb

input:

50
9 27 19 1 31 10 2 7 25 26 12 25 15 18 11 15 30 25 31 2 5 30 8 18 8 17 14 2 17 7 26 26 10 25 26 5 3 5 1 17 18 12 4 17 14 19 30 30 20 2
13 18 3 8 18 11 31 20 21 14 17 29 31 2 5 28 31 17 10 13 6 10 22 18 10 2 0 15 7 14 4 15 25 10 3 30 3 21 0 12 11 19 4 16 27 10 26 3 2 5

output:

27 3
2 15 6 

result:

wrong answer Jury has better answer