Submission #1091563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091563		underwaterkillerwhale	Palindromes (APIO14_palindrome)	C++17	0 / 100	3 ms	348 KiB

palindrome

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 2022; ///loonf mod sai
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int Q;
pii qr[N];

namespace sub1 {
    multiset<int> S;
    void solution () {
        multiset<int> curS;
        rep (i, 1, Q) {
            int typ, X;
            tie(typ, X) = qr[i];
            if (typ == 0) {
                S.insert(X);
            }
            else if (typ == 1) {
                if (S.find(X) != S.end()) S.erase(S.find(X));
            }
            else if (typ == 2) {
                curS.clear();
                iter (&id, S) curS.insert(id ^ X);
                S = curS;
            }
            else {
                ll res = 0, de = 0;
                for (auto it = S.begin(); it != S.end(); ++it) {
                    ++de;
                    res += *it;
                    if (de == X) break;
                }
                cout << res <<"\n";
            }
        }
    }
}

//namespace sub3 {
//    struct tNode {
//        tNode *child[2];
//        ll cnt, sum = 0;
//
//        tNode () {
//            cnt = sum = 0;
//            child[1] = child[0] = NULL;
//        }
//    }*root = new tNode();
//
//    void Add (int X){
//        tNode *cur = root;
//        reb (i, 30, 0) {
//            int bt = bit(X, i);
//            if (cur->child[bt] == NULL) cur->child[bt] = new tNode();
//            cur = cur->child[bt];
//            cur->sum += X;
//            cur->cnt++;
//        }
//    }
//
//    void Del (int X) {
//        tNode *cur = root;
//        reb (i, 30, 0) {
//            int bt = bit(X, i);
//            if (cur->child[bt] == NULL || cur->child[bt]->cnt == 0) return;
//            cur = cur->child[bt];
//        }
//        cur = root;
//        reb (i, 30, 0) {
//            int bt = bit(X, i);
//            cur = cur->child[bt];
//            cur->cnt--;
//            cur->sum -= X;
//        }
//    }
//
//    ll Query (int K, int delta) {
//        if (K == 0) return 0;
//        tNode *cur = root;
//        ll res = 0;
//        reb (i, 30, 0) {
//            ll bt = bit(delta, i);
//            if (cur->child[bt] != NULL) {
//                if (cur->child[bt]->cnt <= K) {
//                    res += cur->child[bt]->sum;
//                    K -= cur->child[bt]->cnt;
//                    if (K == 0) return res;
//                    cur = cur->child[bt ^ 1];
//                }
//                else cur = cur->child[bt];
//            }
//            else cur = cur->child[bt];
//        }
//        res += cur->sum * K;
//        return res;
//    }
//
//    void solution () {
//        int totXor = 0;
//        rep (i, 1, Q) {
//            int typ, X;
//            tie(typ, X) = qr[i];
//            if (typ == 0) {
//                Add(X);
//            }
//            else if (typ == 1) {
//                Del(X ^ totXor);
//            }
//            else if (typ == 2) {
//                totXor ^= X;
//            }
//            else {
//                cout << Query(X, totXor) <<"\n";
//            }
//        }
//    }
//}


void solution() {
    cin >> Q;
    rep (i, 1, Q) {
        cin >> qr[i].fs >> qr[i].se;
    }
    if (Q <= 1000) sub1 :: solution();
//    else
//        sub3 :: solution();
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
    file("XQUERY");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +8
782
1 56
0 1
0 208
0 2
2 637
2 2
2 279
0 2
0 571
0 3
1 396
0 3
0 514
0 3
3 4
3 3
0 590
3 7
0 7
0 4
0 91
0 4
0 551
2 4
1 0
0 5
0 122
0 5
1 417
0 5
0 268
0 5
0 519
3 6
0 186
0 6
0 197
0 6
0 414
0 6
1 465
0 6
1 345
0 6
2 607
2 6
1 168
0 6
3 29
0 7
2 491
3 3
0 541
0 7
0 749
0 7
0 214
2 7
0 650
1 7
0 647
2 7
0 623
3 11
1 342
0 8
0 35
2 8
0 306
0 8
3 0
0 8
1 173
0 8
3 40
0 8
0 159
2 8
2 633
0 8
1 227
0 9
0 143
0 9
3 7
1 9
0 412
3 19
1 482
0 9
3 21
2 9
0 717
2 9
0 469
1 9
2 735
0 9
2 7
2 10
0 347
0 10
3 22
0 10
0 377
0 10
3 38
2 10
3 54
3 29
1 160
1 10
1 352
0 10
0 109
2 10
0 146
0 10
0 450
0 10
0 205
2 11
1 294
0 11
3 5
0 11
0 603
1 11
0 623
0 11
3 59
2 11
2 516
0 11
0 546
0 11
0 173
1 11
2 627
0 11
0 481
2 11
0 492
0 12
0 346
2 12
3 25
0 12
0 472
0 12
0 601
0 12
0 415
3 1
0 269
0 12
1 114
2 12
0 202
1 12
1 335
0 12
0 576
3 8
1 164
1 12
0 660
1 12
2 457
0 13
0 107
3 11
0 102
0 13
0 60
0 13
0 559
3 32
0 353
2 13
0 504
0 13
2 484
3 22
0 637
2 13
2 741
0 13
0 108
0 13
0 256
2 13
1 643
3 38
2 93
0 14
0 205
3 95
1 289
0 14
0 177
2 14
3 14
0 14
3 74
1 14
1 94
3 15
2 166
0 14
2 524
2 14
0 232
2 14
0 149
1 14
0 328
0 14
0 597
1 14
1 554
0 14
3 90
0 14
0 632
0 15
3 55
0 15
3 105
0 15
0 709
0 15
2 197
0 15
0 384
0 15
2 219
2 15
3 13
3 109
3 77
2 15
2 683
1 15
1 174
0 15
0 286
0 15
2 318
1 15
0 521
0 15
1 576
0 15
0 430
0 16
2 66
3 91
2 492
0 16
2 487
1 16
0 688
0 16
3 37
2 16
2 85
3 23
0 92
0 16
0 246
0 16
0 211
2 16
0 480
0 16
0 686
0 16
3 41
0 16
0 430
1 16
3 44
0 16
0 122
0 16
3 16
0 16
0 212
0 17
0 185
2 17
0 552
0 17
2 719
2 17
0 550
1 17
0 539
0 17
0 602
0 17
0 315
3 9
0 676
0 17
0 758
1 17
3 109
2 17
0 684
2 17
0 705
0 17
2 144
2 17
0 503
3 14
3 3
0 17
1 489
0 17
3 18
0 18
0 334
3 74
0 52
2 18
0 59
0 18
0 131
0 18
0 88
3 155
0 167
3 76
0 761
0 18
3 86
0 18
1 360
0 18
3 29
3 86
0 742
3 96
0 685
0 18
2 10
1 18
0 167
0 18
3 114
1 18
0 373
2 18
0 164
3 141
0 716
2 18
0 207
0 19
0 154
1 19
3 59
2 19
0 117
0 19
0 75
2 19
0 450
0 19
2 12
0 19
0 329
1 19
0 513
0 19
0 692
1 19
0 358
0 19
3 53
0 19
0 741
0 19
0 165
0 19
0 566
1 19
0 55
3 13
1 409
0 19
0 577
0 19
2 19
3 1
2 223
2 20
3 144
2 20
0 379
0 20
0 49
0 20
0 238
1 20
2 329
2 20
0 677
0 20
0 626
1 20
0 126
0 20
0 222
0 20
0 178
0 20
0 590
0 20
3 56
0 20
0 617
3 7
0 50
0 20
2 307
0 20
0 240
1 20
0 347
0 20
0 511
0 20
0 496
3 128
0 714
2 20
0 157
0 21
0 345
1 21
0 289
0 21
1 578
3 63
2 622
0 21
0 266
0 21
0 236
2 21
0 547
1 21
0 311
1 21
0 315
0 21
0 669
0 21
1 356
3 223
0 288
1 21
0 211
0 21
0 458
0 21
1 235
3 169
1 148
1 21
1 644
3 76
0 246
2 21
3 22
2 21
2 642
0 21
2 249
1 22
1 153
3 182
1 354
0 22
1 252
0 22
1 378
3 8
0 307
0 22
0 410
2 22
2 258
2 22
3 14
3 122
2 7
0 22
0 636
0 22
0 745
3 194
0 474
1 22
1 102
0 22
0 761
2 22
0 69
0 22
0 182
2 22
0 736
2 22
3 18
0 22
2 172
1 22
0 304
2 22
1 228
3 14
0 735
1 22
0 453
3 208
1 21
2 23
0 561
3 144
2 14
0 23
3 223
3 145
0 250
3 203
3 171
0 23
0 397
0 23
0 52
0 23
0 663
0 23
3 1
0 23
0 515
0 23
0 308
0 23
0 589
0 23
3 164
3 273
0 186
2 23
0 399
0 23
0 696
0 23
3 203
0 23
0 414
3 279
0 664
0 23
3 276
3 236
0 484
0 23
0 85
0 24
0 697
0 24
0 425
0 24
0 770
0 24
0 213
0 24
3 159
3 195
0 657
0 24
0 744
0 24
0 568
1 24
0 389
0 24
3 190
3 110
2 234
2 24
2 516
0 24
0 743
2 24
0 747
0 24
2 649
0 24
1 262
0 24
0 66
1 24
0 717
2 24
0 180
0 24
0 532
2 24
0 94
0 24
0 487
2 24
1 653
0 24
0 580
1 24
0 97
0 25
1 731
2 25
3 67
0 25
3 58
0 25
0 137
0 25
2 33
3 299
0 61
0 25
0 249
0 25
0 517
0 25
0 109
2 25
1 223
0 25
0 355
1 25
0 658
0 25
0 716
0 25
2 457
0 25
1 164
0 25
2 344
0 25
1 210
1 25
0 336
1 25
0 751
0 25
1 282
2 25
2 144
0 25
0 780
3 123
2 353
0 25
3 218
3 196
2 563
2 26
1 10
3 13
3 240
1 26
0 467
0 26
2 68
0 26
0 383
0 26
0 563
0 26
0 204
3 243
0 616
2 26
2 71
3 135
3 211
2 26
0 695
0 26
2 469
0 26
0 358
2 26
3 204
0 26
2 542
1 26
0 81
1 26
0 310
0 26
3 277
0 26
1 425
0 26
2 57
0 26
0 126
0 26
3 245
2 26
0 469
0 26
3 254
0 26
0 679
3 37
0 421
0 26
1 724
1 27
3 236
0 27
0 37
0 27
1 115
0 27
3 102
2 27
0 73
0 27
2 204
1 27
0 494
1 27
0 195
1 27
1 258
0 27
2 497
0 27
1 602
0 27
0 47
3 78
0 104
1 27
0 710
0 27
0 191
0 27
0 438
0 27
0 483
1 27
0 24
0 27
0 41
0 27
0 702
0 27
3 394
0 27
1 351
3 113
0 405
0 27
1 626
2 27
3 317
0 27
1 53
0 27

*/

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:152:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 | #define file(name) freopen(name".inp","r",stdin); \
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:155:5: note: in expansion of macro 'file'
  155 |     file("XQUERY");
      |     ^~~~
palindrome.cpp:153:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 | freopen(name".out","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:155:5: note: in expansion of macro 'file'
  155 |     file("XQUERY");
      |     ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27