Submission #1237564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237564		Lithanium	Broken Device (JOI17_broken_device)	C++20	100 / 100	49 ms	1572 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static ll r[155]={970200092351705732, 417450965574252733, 44492807290717943, 173378208343648389, 1107890608384221875,
    442612236232729421, 743415696134102839, 801238460240262396, 31768310249246727, 218531904734019232,
    420806531509238540, 644515267434214566, 889770800939242606, 235302037444664897, 1113601279628687929,
    112869621397760953, 493571812069726435, 369101320235396346, 177259468093196179, 626341996128209230,
    715689722498393556, 754339150893731961, 761597086023895819, 842075610440508604, 200593412964676443,
    588433355439370907, 374321606849351152, 785161543808675346, 454082280092784988, 1077202199149420966,
    439387969296231807, 790964169388509724, 124321559756054358, 853681538293587726, 790486354816510297,
    204209264016487476, 367032804203938677, 241401379968061704, 736906926164655593, 451579207880835438,
    868701359246987235, 88555483180415628, 658531719888804441, 853254900962537139, 107593851375652309,
    315346883213186384, 66988713062925884, 221563725480548833, 131809750463758034, 154215190305089183,
    253673259183369092, 148832564061606641, 1117102964295916923, 359788123072930203, 506950492793712352,
    42749682957615553, 580638880709292725, 589285449746167516, 652234694624017525, 615246573769401147,
    875337068478482280, 1063364654958477492, 493875257259719114, 423761382427703205, 475664313472693386,
    854379348375551601, 387485520032953802, 941067311034028602, 197643255717512876, 951228463382047781,
    134346045117504160, 242702150211396888, 930448923571189909, 384444700704184840, 213006793033787683,
    772465336715103944, 468220331052020731, 839492833905749816, 36377264579042313, 913948354547091260,
    432438595179040664, 655478837790181153, 61985736445958549, 766165934972559773, 461803531262794626,
    254325779324930456, 1111849044796572615, 466476805762315831, 339304092471166007,
    1066995039434822940, 164427823275434802, 1142486259916015022, 832724269955263614,
    551208315149881002, 8912269745275416, 281269182729082861, 776641710191241933, 176377616612671232,
    899556138813407632, 615159726491879228, 710306654515863508, 710851424324940748, 968359546694674713,
    762985541203546343, 400287621990431792, 617603312005468362, 1113320626778210646, 80163035000491378,
    85800378086004824, 692549380476872734, 706363485632954923, 766864860872288150, 1148002187022177191,
    689221756209224601, 667882393301910971, 118105714600057044, 355747966934176799, 605781954727302900,
    338811020938982092, 477829713958847066, 1068307981012182999, 19016438405631674, 368208997600841075,
    253037214076054641, 854695062323576533, 455831549547503291, 1092033788957937935,
    1147300546529925189, 1069660815702426608, 1127715826505940860, 664833669948459608,
    373479633513207138, 15962303226697117, 546181827572385514, 907412808129061739, 502686904135051896,
    1122407493995784074, 337960126737624383, 84741390805316890, 921490397545709741, 774189650533871617,
    31876756746179798, 204271818043989151, 731860234495895788, 802822321744568084, 173302049670697054,
    889248858569372394, 33484248957505290, 137137912217591007, 389208735314833603};

void Anna(int N, long long X, int K, int P[]) {
    bool dead[155] = {};
    assert(N == 150);
    for (int i = 0; i < K; i ++) dead[P[i]] = 1;
    vector<tuple<ll, ll, ll>> basis; // {reduced, original, mask}
    for (int i = 0; i < N; i ++) if (!dead[i]) {
        ll x = r[i];
        ll og = x;
        ll mask = 0;
        for (int i = 0; i < basis.size(); i ++) {
            auto [a, b, c] = basis[i];
            if (x > (x^a)) {
                x ^= a;
                mask ^= c;
            }
        }
        if (x) {
            mask ^= (1ll << basis.size());
            basis.push_back({x, og, mask});
        } else {
        }
    }
    ll mask = 0;
    set<ll> yes;
    for (auto [a, b, c]:basis) {
        if (X > (X^a)) {
            mask ^= c;
            X ^= a;
        }
    }
    ll tspmo = 0;
    for (int i = 0; i < basis.size(); i ++) if (mask&(1ll << i)) {
        yes.insert(get<1>(basis[i]));
        tspmo ^= get<1>(basis[i]);
    }
    for (int i = 0; i < N; i ++) Set(i, yes.count(r[i]));
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;

bool created = 0;
long long r[155]= {970200092351705732, 417450965574252733, 44492807290717943, 173378208343648389, 1107890608384221875,
    442612236232729421, 743415696134102839, 801238460240262396, 31768310249246727, 218531904734019232,
    420806531509238540, 644515267434214566, 889770800939242606, 235302037444664897, 1113601279628687929,
    112869621397760953, 493571812069726435, 369101320235396346, 177259468093196179, 626341996128209230,
    715689722498393556, 754339150893731961, 761597086023895819, 842075610440508604, 200593412964676443,
    588433355439370907, 374321606849351152, 785161543808675346, 454082280092784988, 1077202199149420966,
    439387969296231807, 790964169388509724, 124321559756054358, 853681538293587726, 790486354816510297,
    204209264016487476, 367032804203938677, 241401379968061704, 736906926164655593, 451579207880835438,
    868701359246987235, 88555483180415628, 658531719888804441, 853254900962537139, 107593851375652309,
    315346883213186384, 66988713062925884, 221563725480548833, 131809750463758034, 154215190305089183,
    253673259183369092, 148832564061606641, 1117102964295916923, 359788123072930203, 506950492793712352,
    42749682957615553, 580638880709292725, 589285449746167516, 652234694624017525, 615246573769401147,
    875337068478482280, 1063364654958477492, 493875257259719114, 423761382427703205, 475664313472693386,
    854379348375551601, 387485520032953802, 941067311034028602, 197643255717512876, 951228463382047781,
    134346045117504160, 242702150211396888, 930448923571189909, 384444700704184840, 213006793033787683,
    772465336715103944, 468220331052020731, 839492833905749816, 36377264579042313, 913948354547091260,
    432438595179040664, 655478837790181153, 61985736445958549, 766165934972559773, 461803531262794626,
    254325779324930456, 1111849044796572615, 466476805762315831, 339304092471166007,
    1066995039434822940, 164427823275434802, 1142486259916015022, 832724269955263614,
    551208315149881002, 8912269745275416, 281269182729082861, 776641710191241933, 176377616612671232,
    899556138813407632, 615159726491879228, 710306654515863508, 710851424324940748, 968359546694674713,
    762985541203546343, 400287621990431792, 617603312005468362, 1113320626778210646, 80163035000491378,
    85800378086004824, 692549380476872734, 706363485632954923, 766864860872288150, 1148002187022177191,
    689221756209224601, 667882393301910971, 118105714600057044, 355747966934176799, 605781954727302900,
    338811020938982092, 477829713958847066, 1068307981012182999, 19016438405631674, 368208997600841075,
    253037214076054641, 854695062323576533, 455831549547503291, 1092033788957937935,
    1147300546529925189, 1069660815702426608, 1127715826505940860, 664833669948459608,
    373479633513207138, 15962303226697117, 546181827572385514, 907412808129061739, 502686904135051896,
    1122407493995784074, 337960126737624383, 84741390805316890, 921490397545709741, 774189650533871617,
    31876756746179798, 204271818043989151, 731860234495895788, 802822321744568084, 173302049670697054,
    889248858569372394, 33484248957505290, 137137912217591007, 389208735314833603};


long long Bruno(int N, int A[]) {
    assert(N == 150);
    long long x = 0;
    for (int i = 0; i < N; i ++) if (A[i]) x ^= r[i];
    return x;
}

• Subtask 1: 100 / 100