oj.uz

Submission #926484

# Submission time Handle Problem Language Result Execution time Memory
926484 2024-02-13T05:59:52 Z Tuanlinh123 Broken Device (JOI17_broken_device) C++17
100 / 100
 53 ms 2932 KB 
#include "Annalib.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

void Anna(int n, long long x, int k, int p[])
{
    pair<ll, bitset<150>> bs[60];
    vector <ll> val={769265534408597608, 684631188613059588, 623939498224436288, 1112438070650928704, 929119508667748969, 931140792598178437, 531220258044890442, 382285151374922194, 757719716505176387, 434067134515960769, 555178854132170424, 365351611811992897, 825766658522166365, 380373830287141453, 912607839045452097, 577020870144153533, 74519899878973361, 324551187055531187, 249744372891951275, 29568047284420190, 647695036731980494, 166961239325119477, 258876185626987212, 791047514679112415, 252485764860936237, 919351983549382415, 222374164717737268, 718053873634401082, 874614520166720438, 325817135050185011, 246109791206259346, 176193287183492976, 1021494683058243197, 94878251762599803, 907801109139356165, 397822671527641406, 21881711217302404, 608565336207687694, 1050832363570729190, 642482206427142373, 1150358639797626899, 109633706099213503, 745889121411498460, 939621337598513383, 1138810479567760642, 1090613195646105780, 696080284823785631, 801692543881015553, 1069995853264342688, 1017420001697510681, 399974841028889439, 781169590729600815, 310565837999361969, 469361682694800169, 845968162694978909, 259455744896090449, 458507481706280523, 1072213831118841956, 558032246532724087, 1123168439594688353, 154659645760287003, 320666410082064059, 720398878589340088, 362035350199674824, 512219398749015053, 1018234900554444801, 800147326153837555, 1001688227840993246, 624538072192681182, 630178385463311555, 652883035192952980, 751234610701746132, 165543845037647733, 277518075785176958, 93604203798981637, 712803802229456281, 1032231587249427780, 50053227451337743, 135357004720869972, 969223313085045770, 177543002251586633, 386639782616917814, 11905056491035226, 891171644176027142, 978304304746038779, 1104093507753908914, 97094350744446499, 36040056773781418, 170603029349846506, 255394618617083456, 1025788098035045501, 1046790951188078435, 510057333880509956, 463409827413944070, 1109450802885274207, 872148098263203362, 884077655594579834, 620325549819998291, 628487963628368376, 915361246398242365, 904269210302259065, 825957834469234605, 134861466066886727, 444134984529799872, 498641268254141814, 51864303353761000, 1032779132794016900, 1078059386754196508, 569046661017912537, 126603272074233778, 86136665846398178, 1050641202025238018, 28194041872684048, 853751522857753480, 1097608057711733069, 767975334751317352, 894219313216287107, 871708328334188927, 361310685693060721, 384630411996976735, 985632941329406970, 868796831398069127, 861336222110175124, 711706714600761016, 581629470431536643, 571376120874919532, 839486628735870091, 179307947736776331, 1133848922900330528, 376053371436608544, 246653667459815269, 628403882110805899, 961239361479489986, 716399153843512303, 214756860857550614, 781501860278856625, 1103664389519342137, 302734259870719650, 461229299874309949, 346251966941437235, 817990443218060935, 963679908488902959, 593087121622114177, 892952370985108473, 992823137715914562, 241358105823696184, 904568012123053123, 943586715810836422, 159635115119781085, 21227821837391212};
    for (ll i=n-1, ptr=k-1; i>=0; i--)
    {
        while (ptr>=0 && p[ptr]==i)
            i--, ptr--;
        if (i<0) break;
        bitset <150> cr; cr.reset(); cr[i]=1;
        for (ll j=59; j>=0; j--)
            if (val[i]&1ll<<j)
            {
                if (bs[j].fi) val[i]^=bs[j].fi, cr^=bs[j].se;
                else {bs[j]={val[i], cr}; break;}
            }
    }
    bitset <150> cr; cr.reset();
    for (ll i=59; i>=0; i--)
        if (x&1ll<<i)
            x^=bs[i].fi, cr^=bs[i].se;
    for (ll i=0; i<n; i++) Set(i, cr[i]);
}

#include "Brunolib.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

long long Bruno(int n, int A[])
{
    vector <ll> val={769265534408597608, 684631188613059588, 623939498224436288, 1112438070650928704, 929119508667748969, 931140792598178437, 531220258044890442, 382285151374922194, 757719716505176387, 434067134515960769, 555178854132170424, 365351611811992897, 825766658522166365, 380373830287141453, 912607839045452097, 577020870144153533, 74519899878973361, 324551187055531187, 249744372891951275, 29568047284420190, 647695036731980494, 166961239325119477, 258876185626987212, 791047514679112415, 252485764860936237, 919351983549382415, 222374164717737268, 718053873634401082, 874614520166720438, 325817135050185011, 246109791206259346, 176193287183492976, 1021494683058243197, 94878251762599803, 907801109139356165, 397822671527641406, 21881711217302404, 608565336207687694, 1050832363570729190, 642482206427142373, 1150358639797626899, 109633706099213503, 745889121411498460, 939621337598513383, 1138810479567760642, 1090613195646105780, 696080284823785631, 801692543881015553, 1069995853264342688, 1017420001697510681, 399974841028889439, 781169590729600815, 310565837999361969, 469361682694800169, 845968162694978909, 259455744896090449, 458507481706280523, 1072213831118841956, 558032246532724087, 1123168439594688353, 154659645760287003, 320666410082064059, 720398878589340088, 362035350199674824, 512219398749015053, 1018234900554444801, 800147326153837555, 1001688227840993246, 624538072192681182, 630178385463311555, 652883035192952980, 751234610701746132, 165543845037647733, 277518075785176958, 93604203798981637, 712803802229456281, 1032231587249427780, 50053227451337743, 135357004720869972, 969223313085045770, 177543002251586633, 386639782616917814, 11905056491035226, 891171644176027142, 978304304746038779, 1104093507753908914, 97094350744446499, 36040056773781418, 170603029349846506, 255394618617083456, 1025788098035045501, 1046790951188078435, 510057333880509956, 463409827413944070, 1109450802885274207, 872148098263203362, 884077655594579834, 620325549819998291, 628487963628368376, 915361246398242365, 904269210302259065, 825957834469234605, 134861466066886727, 444134984529799872, 498641268254141814, 51864303353761000, 1032779132794016900, 1078059386754196508, 569046661017912537, 126603272074233778, 86136665846398178, 1050641202025238018, 28194041872684048, 853751522857753480, 1097608057711733069, 767975334751317352, 894219313216287107, 871708328334188927, 361310685693060721, 384630411996976735, 985632941329406970, 868796831398069127, 861336222110175124, 711706714600761016, 581629470431536643, 571376120874919532, 839486628735870091, 179307947736776331, 1133848922900330528, 376053371436608544, 246653667459815269, 628403882110805899, 961239361479489986, 716399153843512303, 214756860857550614, 781501860278856625, 1103664389519342137, 302734259870719650, 461229299874309949, 346251966941437235, 817990443218060935, 963679908488902959, 593087121622114177, 892952370985108473, 992823137715914562, 241358105823696184, 904568012123053123, 943586715810836422, 159635115119781085, 21227821837391212};
    ll ans=0;
    for (ll i=0; i<n; i++)
        if (A[i]) ans^=val[i];
    return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2364 KB Output is correct - L* = 40
2 Correct 45 ms 2384 KB Output is correct - L* = 40
3 Correct 45 ms 2592 KB Output is correct - L* = 40
4 Correct 46 ms 2304 KB Output is correct - L* = 40
5 Correct 46 ms 2564 KB Output is correct - L* = 40
6 Correct 45 ms 2364 KB Output is correct - L* = 40
7 Correct 45 ms 2568 KB Output is correct - L* = 40
8 Correct 45 ms 2372 KB Output is correct - L* = 40
9 Correct 45 ms 2520 KB Output is correct - L* = 40
10 Correct 45 ms 2404 KB Output is correct - L* = 40
11 Correct 46 ms 2560 KB Output is correct - L* = 40
12 Correct 47 ms 2400 KB Output is correct - L* = 40
13 Correct 49 ms 2348 KB Output is correct - L* = 40
14 Correct 47 ms 2700 KB Output is correct - L* = 40
15 Correct 47 ms 2424 KB Output is correct - L* = 40
16 Correct 52 ms 2396 KB Output is correct - L* = 40
17 Correct 46 ms 2296 KB Output is correct - L* = 40
18 Correct 49 ms 2296 KB Output is correct - L* = 40
19 Correct 46 ms 2484 KB Output is correct - L* = 40
20 Correct 46 ms 2528 KB Output is correct - L* = 40
21 Correct 53 ms 2300 KB Output is correct - L* = 40
22 Correct 45 ms 2312 KB Output is correct - L* = 40
23 Correct 46 ms 2308 KB Output is correct - L* = 40
24 Correct 45 ms 2300 KB Output is correct - L* = 40
25 Correct 46 ms 2296 KB Output is correct - L* = 40
26 Correct 46 ms 2320 KB Output is correct - L* = 40
27 Correct 49 ms 2300 KB Output is correct - L* = 40
28 Correct 45 ms 2548 KB Output is correct - L* = 40
29 Correct 48 ms 2464 KB Output is correct - L* = 40
30 Correct 46 ms 2308 KB Output is correct - L* = 40
31 Correct 46 ms 2312 KB Output is correct - L* = 40
32 Correct 45 ms 2376 KB Output is correct - L* = 40
33 Correct 45 ms 2528 KB Output is correct - L* = 40
34 Correct 46 ms 2364 KB Output is correct - L* = 40
35 Correct 46 ms 2356 KB Output is correct - L* = 40
36 Correct 45 ms 2420 KB Output is correct - L* = 40
37 Correct 45 ms 2508 KB Output is correct - L* = 40
38 Correct 45 ms 2592 KB Output is correct - L* = 40
39 Correct 47 ms 2932 KB Output is correct - L* = 40
40 Correct 45 ms 2384 KB Output is correct - L* = 40