QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111290#1899. Maximaze XOR sumanhduc2701WA 6ms3712kbC++232.4kb2023-06-06 16:47:052023-06-06 16:47:09

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:47:09]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3712kb
  • [2023-06-06 16:47:05]
  • 提交

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) (1LL & ((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];
    }
    for (int i = 1; i <= n; 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] << " ";
        }
    }
}

详细

Test #1:

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

input:

2
1 1
2 2

output:

6 1
1 

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: 3496kb

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: 0
Accepted
time: 1ms
memory: 3488kb

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:

35 0

result:

ok n=50

Test #5:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

100
50 13 42 41 8 21 50 18 21 50 9 27 51 10 43 26 29 6 52 44 52 19 39 47 59 35 42 6 27 41 8 25 32 32 45 18 57 5 46 32 60 24 63 56 31 32 58 15 0 36 31 33 31 50 14 45 31 27 15 55 8 53 10 5 8 24 15 35 45 34 16 31 44 51 34 13 30 49 0 4 62 6 8 30 44 29 59 60 45 40 1 0 40 29 35 18 42 52 15 28
35 43 24 14 ...

output:

77 2
2 3 

result:

ok n=100

Test #6:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

239
102 34 53 67 127 99 16 79 25 9 34 91 63 46 1 27 47 66 54 90 93 10 60 118 110 27 5 95 62 99 117 28 90 33 101 69 7 104 33 10 57 32 106 42 28 5 117 125 15 38 107 107 36 103 103 115 34 127 123 37 3 123 43 40 118 57 112 53 94 110 54 26 81 33 94 55 25 45 61 4 55 67 27 10 91 102 53 101 109 109 60 73 8 ...

output:

243 3
1 2 4 

result:

ok n=239

Test #7:

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

input:

322
167 3 23 89 165 131 48 207 116 214 246 1 39 79 196 84 123 132 211 177 76 209 197 5 30 214 29 193 149 245 196 90 253 213 134 202 195 226 147 13 249 202 254 165 214 1 65 23 52 62 184 108 16 252 33 177 14 250 34 119 243 187 195 83 41 7 240 95 62 104 248 184 101 174 17 254 243 108 209 215 227 120 18...

output:

397 3
3 5 4 

result:

ok n=322

Test #8:

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

input:

654
456 150 36 391 6 195 17 37 56 92 403 225 374 294 447 267 112 149 125 225 485 86 262 25 301 197 108 91 176 375 18 453 109 434 48 358 116 240 80 451 364 352 468 340 270 101 110 264 167 277 165 189 410 187 87 457 476 341 305 372 119 22 313 379 7 485 325 143 320 477 385 212 358 459 493 98 211 179 22...

output:

612 2
5 2 

result:

ok n=654

Test #9:

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

input:

1000
141 295 799 239 546 573 90 163 285 348 277 944 836 925 584 691 480 831 174 427 574 36 326 125 559 83 467 880 136 116 349 946 419 87 174 977 989 877 726 66 22 333 424 989 564 561 571 94 416 886 361 742 454 32 83 121 666 339 219 638 270 731 552 834 925 933 294 629 708 580 259 427 387 365 947 220 ...

output:

1973 3
2 7 9 

result:

ok n=1000

Test #10:

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

input:

1234
261 1657 517 1483 1960 89 1370 670 410 1340 1722 1381 995 1916 604 2043 779 1686 59 1953 1951 1966 150 1402 688 1545 112 1806 595 912 1553 1739 1570 339 1411 1151 953 4 1301 1503 826 120 476 1796 970 1066 1069 745 17 1464 1061 1006 702 356 1569 1112 769 1428 1862 1742 271 850 506 1758 674 1740 ...

output:

2771 2
1 3 

result:

ok n=1234

Test #11:

score: 0
Accepted
time: 3ms
memory: 3496kb

input:

4321
954480449 587144652 757102525 355665537 828579167 331077434 432524612 696971489 994830414 712338630 893352505 861729750 502105584 1035097357 411845405 686198569 310059262 611729823 534618751 260487378 956262276 516622722 333379461 165343106 889332064 1032610733 563086441 612113690 937039558 168...

output:

1905476326 8
3 4 7 6 8 10 17 15 

result:

ok n=4321

Test #12:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

7890
167365278745 53574745863 1083471078178 94877662306 414150779087 732017494615 268662798673 640482866772 813746165313 1039118737841 317126232364 273209176527 260850168401 122195402366 173566316456 703789564575 840725477414 416413225738 483521349439 1015327498161 438272982188 180451885829 54687593...

output:

1241550719429 5
6 9 16 13 11 

result:

ok n=7890

Test #13:

score: -100
Wrong Answer
time: 4ms
memory: 3592kb

input:

10000
1024699458171845 273191988760302 672954995688326 856568833018077 965082229777704 277750079399023 667877391291263 435567952575490 586753361866430 328361268020042 1013607754170263 601702869301405 1104383095207561 1094567873246657 910010660363394 921121581843645 908188549630208 527368341706711 95...

output:

2243904366424282 9
1 2 9 5 6 10 8 14 16 12 20 19 24 27 26 29 

result:

wrong answer Wrong sum