oj.uz

Submission #385945

# Submission time Handle Problem Language Result Execution time Memory
385945 2021-04-05T09:13:22 Z ACmachine Broken Device (JOI17_broken_device) C++17
100 / 100
 82 ms 2956 KB 
#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//mt19937_64 rng(time(NULL));
void Anna( int N, long long X, int K, int P[] ){
    vector<ll> random = {3546421266716138234, 4118921917702196035, 2700836428776168254, 8637678521909238612, 4427571401241844645, 7229506091524075051, 8404546367687262874, 4605914583369335667, 5585125593649921414, 594983612610587848, 6837615286782809079, 3434747081785985231, 2035182858803818122, 6416356531244053205, 1621717194677673165, 1299635426806367314, 1238523415348761644, 4152322633981407546, 9097002777001214116, 8337876818544295893, 7690427813128167022, 6987411890468762612, 5976642730985964956, 5556684797814726947, 2428782802807121823, 292561756601624241, 6324417021993039592, 427126368896763749, 6974864267426184047, 6750361625678243665, 1343861354644658637, 7581795984860133440, 7415494328160126127, 5167510663767251910, 2177725726105845771, 9212476336301602021, 706715215185726862, 4129168797106835817, 2559669550800171143, 3079145299298425877, 2278971142799717079, 2825161840234474214, 3166102579593990155, 2583068538248832008, 2481797574848695853, 8372908961003360590, 5619782884176208978, 4612050518156736310, 5697447238279349914, 6625514754358046473, 2660251965621357128, 8407489204450815294, 37249501608412866, 2617389539822824692, 8235453935452354262, 6567410745018123737, 2521220850120896290, 4822485043178907550, 2096801645831794153, 2191444845107412305, 5247664863650115473, 7817188256070508645, 5995916190164641993, 9157734521548388024, 2595698277880873389, 5107112578125508720, 5475302298216536766, 5018099708486183557, 1151347153580395314, 6475687414554403303, 1099934285193173086, 3471673167364575052, 4337036548435890409, 1421750628032894652, 8843511814128000853, 1179956838433530436, 7681279471845466038, 2307892327910040325, 5649666154373788009, 3154187379399796461, 3248407529975251508, 7098880324397390601, 3138160516352570778, 5026179851597500764, 367371892782165064, 9195219991360239246, 6149984063278149998, 7696789908439800121, 3153611702756862384, 5235561455402641783, 1768403027948825580, 6784358508221829559, 2474414058918334381, 5923184559193404831, 1090822925914804424, 4204225300342542543, 3904111112834682790, 7014534586805647937, 6008067598330921356, 3742121772452412602, 5291485477062417629, 3078967541208736815, 3283873193555992212, 914912763543776384, 5487257983771532200, 2525534012814558969, 341551256086059576, 1107091603706901054, 7956943650016384620, 5149263258461310704, 84247500798612810, 7265998129762874012, 8492838065349448582, 7822803958592711496, 4828755127691544864, 7093932268030210898, 2824348260804893440, 6046092798462613626, 6861071134841516807, 4059603212688431629, 1973895044298901385, 6832067832969494789, 7794706987630831831, 1538754142709807334, 2718162448967718406, 8775382669440170709, 3448507225105208078, 2904247231010056204, 5402170661566980484, 982519054780047970, 340186042780985180, 7440180641889954559, 4373641485152155877, 4114690706538192003, 8238865277262726161, 175728996655791149, 4910851212624271124, 4782536583827005544, 8803294367235145610, 4905225410682802964, 4045207710780978646, 750390776526795946, 689492048244657225, 7356811354858178571, 6011147855843514337, 8862618829447926278, 2232923547416258788, 8738769403155010516, 2593035371780470259, 951137016218255338 };
    //for(int i = 0; i < 150; ++i){
        //random[i] = rng();
    //}
    vector<bool> removed(150, false);
    for(int i = 0; i < K; ++i){
        removed[P[i]] = true;
    }
    vector<ll> basis(64, -1);
    vector<bitset<150>> how(64);
    auto insert = [&](ll v, bitset<150> &mask){
        for(int i = 62; i >= 0; --i){
            if(v &(1ll << i)){
                if(basis[i] == -1){
                    basis[i] = v;
                    how[i] = mask;
                    return;
                }
                else{
                    v ^= basis[i];
                    mask ^= how[i];
                }
            }
        }
    };
    auto find = [&](ll x){
        bitset<150> res; res.reset();
        for(int i = 62; i >= 0; --i){
            if(x & (1ll << i)){
                x^= basis[i];
                res ^= how[i];
            }
        }
        return res;
    };
    for(int i = 0; i < 150; ++i){
        if(!removed[i]){
            bitset<150> tm; tm.reset();
            tm[i] = 1;
            insert(random[i], tm);
        }
    }
    bitset<150> res = find(X);
    for(int i = 0; i < 150; ++i){
        if(res[i]){
            Set(i, 1);
        }
        else{
            Set(i, 0);
        }
    }

}

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937_64 rng(time(NULL));
long long Bruno( int N, int A[]){
    vector<ll> random ={3546421266716138234, 4118921917702196035, 2700836428776168254, 8637678521909238612, 4427571401241844645, 7229506091524075051, 8404546367687262874, 4605914583369335667, 5585125593649921414, 594983612610587848, 6837615286782809079, 3434747081785985231, 2035182858803818122, 6416356531244053205, 1621717194677673165, 1299635426806367314, 1238523415348761644, 4152322633981407546, 9097002777001214116, 8337876818544295893, 7690427813128167022, 6987411890468762612, 5976642730985964956, 5556684797814726947, 2428782802807121823, 292561756601624241, 6324417021993039592, 427126368896763749, 6974864267426184047, 6750361625678243665, 1343861354644658637, 7581795984860133440, 7415494328160126127, 5167510663767251910, 2177725726105845771, 9212476336301602021, 706715215185726862, 4129168797106835817, 2559669550800171143, 3079145299298425877, 2278971142799717079, 2825161840234474214, 3166102579593990155, 2583068538248832008, 2481797574848695853, 8372908961003360590, 5619782884176208978, 4612050518156736310, 5697447238279349914, 6625514754358046473, 2660251965621357128, 8407489204450815294, 37249501608412866, 2617389539822824692, 8235453935452354262, 6567410745018123737, 2521220850120896290, 4822485043178907550, 2096801645831794153, 2191444845107412305, 5247664863650115473, 7817188256070508645, 5995916190164641993, 9157734521548388024, 2595698277880873389, 5107112578125508720, 5475302298216536766, 5018099708486183557, 1151347153580395314, 6475687414554403303, 1099934285193173086, 3471673167364575052, 4337036548435890409, 1421750628032894652, 8843511814128000853, 1179956838433530436, 7681279471845466038, 2307892327910040325, 5649666154373788009, 3154187379399796461, 3248407529975251508, 7098880324397390601, 3138160516352570778, 5026179851597500764, 367371892782165064, 9195219991360239246, 6149984063278149998, 7696789908439800121, 3153611702756862384, 5235561455402641783, 1768403027948825580, 6784358508221829559, 2474414058918334381, 5923184559193404831, 1090822925914804424, 4204225300342542543, 3904111112834682790, 7014534586805647937, 6008067598330921356, 3742121772452412602, 5291485477062417629, 3078967541208736815, 3283873193555992212, 914912763543776384, 5487257983771532200, 2525534012814558969, 341551256086059576, 1107091603706901054, 7956943650016384620, 5149263258461310704, 84247500798612810, 7265998129762874012, 8492838065349448582, 7822803958592711496, 4828755127691544864, 7093932268030210898, 2824348260804893440, 6046092798462613626, 6861071134841516807, 4059603212688431629, 1973895044298901385, 6832067832969494789, 7794706987630831831, 1538754142709807334, 2718162448967718406, 8775382669440170709, 3448507225105208078, 2904247231010056204, 5402170661566980484, 982519054780047970, 340186042780985180, 7440180641889954559, 4373641485152155877, 4114690706538192003, 8238865277262726161, 175728996655791149, 4910851212624271124, 4782536583827005544, 8803294367235145610, 4905225410682802964, 4045207710780978646, 750390776526795946, 689492048244657225, 7356811354858178571, 6011147855843514337, 8862618829447926278, 2232923547416258788, 8738769403155010516, 2593035371780470259, 951137016218255338 } ;
    //cout << "{";
    //for(int i = 0; i < 150; ++i){
        //cout << abs((ll)rng()) <<  ", ";
    //}
    //cout <<"}";
    ll ans = 0;
    for(int i = 0; i < 150; ++i){
        if(A[i] == 1){
            ans ^= random[i];
        }
    }

  return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2948 KB Output is correct - L* = 40
2 Correct 72 ms 2744 KB Output is correct - L* = 40
3 Correct 71 ms 2956 KB Output is correct - L* = 40
4 Correct 73 ms 2868 KB Output is correct - L* = 40
5 Correct 71 ms 2840 KB Output is correct - L* = 40
6 Correct 72 ms 2744 KB Output is correct - L* = 40
7 Correct 80 ms 2744 KB Output is correct - L* = 40
8 Correct 72 ms 2832 KB Output is correct - L* = 40
9 Correct 71 ms 2692 KB Output is correct - L* = 40
10 Correct 72 ms 2620 KB Output is correct - L* = 40
11 Correct 73 ms 2692 KB Output is correct - L* = 40
12 Correct 75 ms 2496 KB Output is correct - L* = 40
13 Correct 77 ms 2620 KB Output is correct - L* = 40
14 Correct 73 ms 2620 KB Output is correct - L* = 40
15 Correct 75 ms 2700 KB Output is correct - L* = 40
16 Correct 74 ms 2492 KB Output is correct - L* = 40
17 Correct 72 ms 2620 KB Output is correct - L* = 40
18 Correct 73 ms 2492 KB Output is correct - L* = 40
19 Correct 73 ms 2620 KB Output is correct - L* = 40
20 Correct 73 ms 2664 KB Output is correct - L* = 40
21 Correct 73 ms 2700 KB Output is correct - L* = 40
22 Correct 72 ms 2492 KB Output is correct - L* = 40
23 Correct 72 ms 2620 KB Output is correct - L* = 40
24 Correct 71 ms 2620 KB Output is correct - L* = 40
25 Correct 72 ms 2492 KB Output is correct - L* = 40
26 Correct 71 ms 2620 KB Output is correct - L* = 40
27 Correct 72 ms 2716 KB Output is correct - L* = 40
28 Correct 72 ms 2492 KB Output is correct - L* = 40
29 Correct 82 ms 2692 KB Output is correct - L* = 40
30 Correct 74 ms 2496 KB Output is correct - L* = 40
31 Correct 72 ms 2692 KB Output is correct - L* = 40
32 Correct 70 ms 2620 KB Output is correct - L* = 40
33 Correct 71 ms 2492 KB Output is correct - L* = 40
34 Correct 71 ms 2492 KB Output is correct - L* = 40
35 Correct 73 ms 2700 KB Output is correct - L* = 40
36 Correct 75 ms 2492 KB Output is correct - L* = 40
37 Correct 72 ms 2700 KB Output is correct - L* = 40
38 Correct 72 ms 2760 KB Output is correct - L* = 40
39 Correct 75 ms 2664 KB Output is correct - L* = 40
40 Correct 71 ms 2492 KB Output is correct - L* = 40