Submission #753729

#	Time	Username	Problem	Language	Result	Execution time	Memory
753729		piOOE	Broken Device (JOI17_broken_device)	C++17	100 / 100	74 ms	2704 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

namespace {
    vector<ll> p = {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};

    using Bitset = bitset<150>;
}

void Anna(int N, long long X, int K, int P[]) {
    vector<int> used(N);

    for (int i = 0; i < K; ++i) {
        used[P[i]] = true;
    }

    vector<ll> basis;
    vector<Bitset> st;

    auto query = [&](ll x) -> pair<ll, Bitset> {
        Bitset now{};

        for (int i = 0; i < size(basis); ++i) {
            if ((x ^ basis[i]) < x) {
                x ^= basis[i];
                now ^= st[i];
            }
        }

        return {x, now};
    };

    for (int j = 0; j < N; ++j) {
        if (used[j]) {
            continue;
        }

        auto [x, now] = query(p[j]);

        if (x > 0) {
            now[j] = true;
            basis.push_back(x);
            st.push_back(now);
        }
    }

    auto [x, ans] = query(X);

    assert(x == 0);

    for (int i = 0; i < N; i++) {
        Set(i, ans[i]);
    }
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

namespace {
    vector<ll> p = {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[]) {
    ll X = 0;

    for (int i = 0; i < N; ++i) {
        if (A[i]) {
            X ^= p[i];
        }
    }

    return X;
}

Compilation message (stderr)

Anna.cpp: In lambda function:
Anna.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < size(basis); ++i) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100