— Dark mode

KILO 2016 3/5

XOR

  • Start: 2016-09-20 16:30:00
  • End: 2016-09-20 19:00:00
Submission details
Task:XOR
Sender::]
Submission time:2016-09-20 17:08:22 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.06 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.05 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.52 sdetails
#12ACCEPTED0.52 sdetails
#13ACCEPTED0.52 sdetails
#14ACCEPTED0.53 sdetails
#15ACCEPTED0.52 sdetails
#16ACCEPTED0.53 sdetails
#17ACCEPTED0.52 sdetails
#18ACCEPTED0.52 sdetails
#19ACCEPTED0.51 sdetails
#20ACCEPTED0.52 sdetails
#21ACCEPTED0.50 sdetails
#22ACCEPTED0.52 sdetails
#23ACCEPTED0.51 sdetails
#24ACCEPTED0.49 sdetails
#25ACCEPTED0.52 sdetails
#26ACCEPTED0.52 sdetails
#27ACCEPTED0.52 sdetails
#28ACCEPTED0.52 sdetails
#29ACCEPTED0.52 sdetails
#30ACCEPTED0.53 sdetails
#31ACCEPTED0.06 sdetails
#32ACCEPTED0.06 sdetails

Compiler report

input/code.cpp: In function 'void rev(std::vector<long unsigned int>&)':
input/code.cpp:6:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); ++i) {
                                ^

Code

#include<bits/stdc++.h>

using namespace std;

void rev(vector<uint64_t> &b) {
    for (int i = 0; i < b.size(); ++i) {
        uint64_t tmp = 0;
        uint64_t k = (uint64_t)1<<(uint64_t)62;
        for (uint64_t j = 1; j <= (uint64_t)1<<(uint64_t)62; j*=2) {
            if (b[i]&j) {
                tmp += k;
            }
            k/=2;
        }
        b[i] = tmp;
    }
}

int main() {
    uint64_t q;
    cin >> q;

    vector<uint64_t> basis;

    bool has0 = false;

    for (uint64_t i = 0; i < q; ++i) {
        uint64_t t, x;
        cin >> t >> x;
        /*cout << "Basis: " << endl;
        for (auto b: basis) cout << b << ' ';
        cout << endl;*/
        if (t == 1) {
            for (uint64_t j = 0; j < basis.size(); ++j) {
                if (x & (basis[j] & (-basis[j]))) {
                    x^=basis[j];
                }
            }
            if (x != 0) {
                basis.push_back(x);
                //cout << "Adding: " << x << endl;
                rev(basis);
                sort(basis.rbegin(), basis.rend());
                rev(basis);
            } else {
                has0 = true;
            }
        } else {
            if (x == 0) {
                if (has0) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            } else {
                for (uint64_t j = 0; j < basis.size(); ++j) {
                    if (x & (basis[j] & (-basis[j]))) {
                        x^=basis[j];
                    }
                }
                if (x == 0) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
59
2 549796
1 797427
2 8267
2 94241
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 2

Verdict: ACCEPTED

input
60
2 189273
2 88019
2 110069
1 611607
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 3

Verdict: ACCEPTED

input
86
1 811855
1 110105
2 569085
1 805175
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 4

Verdict: ACCEPTED

input
79
2 204680
2 479640
2 21734
1 822295
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 5

Verdict: ACCEPTED

input
54
2 393529
2 508737
2 279234
1 610723
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 6

Verdict: ACCEPTED

input
76
1 40087
1 746813
1 120910
2 1048513
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 7

Verdict: ACCEPTED

input
73
1 96148
1 881120
1 414495
1 814692
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 8

Verdict: ACCEPTED

input
93
2 458578
1 907441
2 406032
2 72125
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 9

Verdict: ACCEPTED

input
66
1 256689
1 656847
1 204470
1 706678
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 10

Verdict: ACCEPTED

input
90
1 806402
2 212552
2 588349
2 437562
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 11

Verdict: ACCEPTED

input
500000
1 87911
1 254464
2 936765
2 177725
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 12

Verdict: ACCEPTED

input
500000
2 580798
2 711232
1 517084
1 706145
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 13

Verdict: ACCEPTED

input
500000
1 890696
1 736663
1 309693
1 877748
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 14

Verdict: ACCEPTED

input
500000
2 422535
2 915569
1 799087
1 640406
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 15

Verdict: ACCEPTED

input
500000
1 173418
2 945329
1 54964
2 617017
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 16

Verdict: ACCEPTED

input
500000
1 193460
2 476498
2 117697
1 176455
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 17

Verdict: ACCEPTED

input
500000
2 88645
2 524394
1 545883
2 906204
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 18

Verdict: ACCEPTED

input
500000
1 349059
2 820258
1 666916
1 821504
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 19

Verdict: ACCEPTED

input
500000
1 55427
1 389186
2 340527
1 451535
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 20

Verdict: ACCEPTED

input
500000
2 186
2 572852
2 279886
1 559531
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 21

Verdict: ACCEPTED

input
500000
1 759956
2 946637
2 781536
1 211151
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 22

Verdict: ACCEPTED

input
500000
2 898884
1 461135
1 129061
2 1011354
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 23

Verdict: ACCEPTED

input
500000
1 124677
2 379713
1 1034177
1 152116
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 24

Verdict: ACCEPTED

input
500000
2 280923
1 888416
1 301451
2 877860
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 25

Verdict: ACCEPTED

input
500000
2 239639
1 863577
2 825271
2 1030489
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 26

Verdict: ACCEPTED

input
500000
2 842792
1 280374
2 528173
2 902772
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 27

Verdict: ACCEPTED

input
500000
1 769700
2 786489
2 954187
2 213653
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 28

Verdict: ACCEPTED

input
500000
2 45666
2 742846
1 870697
2 824087
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 29

Verdict: ACCEPTED

input
500000
2 1010353
1 298819
1 946132
2 1017161
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 30

Verdict: ACCEPTED

input
500000
2 195272
1 971250
1 118355
2 361142
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 31

Verdict: ACCEPTED

input
4
2 0
1 5
1 5
2 0
view save

correct output
NO
YES
view save

user output
NO
YES
view save

Test 32

Verdict: ACCEPTED

input
3
2 0
1 0
2 0
view save

correct output
NO
YES
view save

user output
NO
YES
view save

Tasks

A XORB Secret societyC Ice creamD Time bombE Palindrome

Submissions (:])

2016-09-20 17:08:22