# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1237553 | Lithanium | Broken Device (JOI17_broken_device) | C++20 | 50 ms | 1344 KiB |
#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});
}
}
ll mask = 0;
set<ll> yes;
for (auto [a, b, c]:basis) {
if (X > (X^a)) {
mask |= c;
X ^= a;
}
}
assert(X == 0);
for (int i = 0; i < basis.size(); i ++) if (mask&(1ll << i)) yes.insert(get<1>(basis[i]));
for (int i = 0; i < N; i ++) Set(i, yes.count(r[i]));
}
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |