QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314155 | #7303. City United | zdczdc | TL | 577ms | 13020kb | C++20 | 1.0kb | 2024-01-25 13:34:56 | 2024-01-25 13:34:56 |
Judging History
answer
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[(r) + 1]
using namespace std;
void file(){
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
}
using ll = long long;
const int sMax = 4'782'969;
int n, m;
array<int, 16> pw;
array<vector<int>, 55> g;
array<bool, sMax> f, tf;
int main(){
// file();
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
pw[0] = 1;
for(int i = 1; i <= 15; i++) pw[i] = 3 * pw[i - 1];
for(int i = 1, u, v; i <= m; i++){
cin >> u >> v;
if(u < v) swap(u, v);
g[u].push_back(v);
}
tf[0] = 1;
bool rs = 0;
for(int i = 0; i <= n; i++, tf = f){
f.fill(0);;
for(int S = 0; S < sMax; S++){
if(!tf[S]) continue;
if((S % 3) == 1) rs ^= 1;
vector<int> cnt(3, 0);
for(int to : g[i + 1]) cnt[(S / pw[i - to]) % 3]++;
if(!cnt[2]) f[(S * 3 + 1) % sMax] ^= 1;
if(!cnt[1]) f[(S * 3 + 2) % sMax] ^= 1;
f[(S * 3) % sMax] ^= 1;
}
}
cout << rs << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 13016kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 15ms
memory: 12948kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 54ms
memory: 12896kb
input:
15 31 9 5 14 5 2 7 5 15 11 14 11 9 2 6 3 4 12 1 6 8 3 5 11 10 15 6 4 1 1 2 8 9 6 12 14 10 13 2 4 5 3 8 3 15 11 6 7 5 4 6 11 2 13 15 3 2 8 4 6 13 7 10
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 57ms
memory: 12952kb
input:
15 92 10 9 15 7 11 1 7 2 12 10 1 12 4 13 1 4 11 5 1 2 4 3 1 9 15 4 11 7 14 1 8 7 8 12 7 4 10 14 7 13 6 13 4 12 11 10 13 8 13 15 10 7 2 14 12 13 14 5 8 4 12 9 7 9 15 10 10 4 11 15 13 10 6 15 8 9 2 8 11 12 5 4 1 6 2 9 10 1 5 6 14 12 5 13 5 10 6 9 15 8 12 15 10 2 5 7 4 6 2 11 12 3 15 9 9 3 3 10 5 2 12 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 55ms
memory: 12952kb
input:
15 80 5 10 10 13 13 4 4 2 6 10 8 6 13 7 13 9 9 5 6 13 6 3 13 14 10 12 8 3 8 13 9 1 7 5 14 6 14 10 6 9 11 14 7 10 13 15 7 9 14 7 8 1 10 3 11 6 15 7 12 8 3 13 6 2 6 7 13 5 7 3 11 8 3 5 2 5 15 2 7 12 1 14 11 1 1 10 10 4 4 14 2 9 12 5 15 8 8 5 1 13 1 12 9 14 14 2 1 3 14 5 10 15 3 15 1 7 1 5 6 15 8 9 2 7...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 52ms
memory: 12864kb
input:
15 45 13 15 3 15 5 4 15 14 6 10 2 3 10 11 9 8 8 7 10 4 9 2 3 8 15 2 2 6 15 9 6 15 10 7 8 2 5 6 14 10 12 10 8 1 11 3 3 12 2 1 11 15 11 5 2 7 1 11 8 4 1 6 14 5 5 2 13 1 7 11 4 12 12 14 15 5 7 5 10 2 4 7 13 2 4 14 12 1 12 11
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 61ms
memory: 13020kb
input:
15 48 5 14 11 1 6 8 10 3 10 6 3 4 3 8 15 3 10 15 2 11 5 15 7 10 7 14 5 10 2 9 9 3 11 4 11 7 12 5 9 10 10 14 10 2 13 11 2 8 10 13 2 3 7 12 13 3 10 8 12 10 15 12 4 7 9 13 7 13 5 7 2 13 11 14 9 15 6 15 8 12 2 6 1 13 3 14 4 15 5 3 6 3 4 10 2 7
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 55ms
memory: 12956kb
input:
15 104 9 1 11 4 11 6 2 14 8 3 10 6 1 4 8 5 4 15 10 4 12 4 14 11 7 9 12 15 1 10 13 14 9 14 1 6 4 2 2 9 5 10 14 10 2 10 12 6 3 10 9 5 1 7 12 14 5 2 10 13 7 6 6 8 10 15 8 14 14 5 9 12 1 3 12 10 10 9 6 14 8 7 8 11 10 11 13 6 11 5 12 3 3 13 11 9 7 12 8 1 11 12 15 8 8 12 9 13 8 9 14 7 7 11 3 7 3 11 14 3 1...
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 51ms
memory: 12952kb
input:
15 102 9 8 7 5 2 3 5 14 15 7 7 9 15 11 14 15 13 7 4 1 3 6 8 14 4 7 12 7 10 1 13 5 2 8 8 12 10 9 5 3 14 1 10 8 10 14 13 3 6 9 6 12 1 3 10 5 2 15 8 13 8 4 1 7 6 13 5 2 14 9 6 2 6 11 2 1 11 9 1 12 6 14 14 13 10 7 1 6 3 7 12 10 12 13 12 5 12 2 12 14 4 9 3 9 13 11 11 10 5 1 10 15 8 7 6 7 13 2 6 5 8 6 11 ...
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 61ms
memory: 12872kb
input:
15 104 3 4 11 8 5 13 8 7 9 4 7 11 3 2 6 11 10 4 9 7 3 12 11 2 1 11 5 12 1 10 5 6 6 7 2 10 12 14 1 14 13 11 1 3 9 8 6 13 10 14 1 7 11 10 11 14 6 8 11 9 12 13 15 7 9 3 13 4 3 14 12 7 2 4 10 9 10 7 2 1 15 9 6 15 12 9 14 7 7 3 12 15 11 3 3 10 4 6 5 11 10 5 11 15 13 10 6 1 10 12 12 11 4 7 10 8 4 1 13 2 3...
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 51ms
memory: 12924kb
input:
15 91 1 11 15 14 14 11 5 10 4 6 6 10 11 3 14 5 15 10 3 2 11 5 9 13 11 12 15 5 13 12 3 7 2 4 12 2 10 13 7 8 9 11 8 11 3 5 3 10 8 3 14 10 2 7 12 15 3 6 6 9 8 4 6 2 8 1 7 10 5 1 7 6 4 1 10 2 11 4 1 13 12 14 11 6 9 3 9 5 14 3 14 9 8 14 9 8 4 3 1 7 15 3 13 3 4 15 15 8 5 4 14 1 10 9 13 7 12 7 7 15 9 2 6 1...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 56ms
memory: 12896kb
input:
15 103 13 9 2 6 13 1 7 6 1 3 3 7 1 14 9 3 4 5 14 8 14 13 10 9 13 4 12 10 14 15 1 4 11 10 8 7 7 11 6 9 14 6 10 5 1 8 11 8 7 2 5 6 5 3 2 10 1 11 3 4 7 13 14 3 4 10 12 5 9 12 5 1 1 6 12 2 2 11 9 1 1 7 8 9 10 15 3 2 7 10 2 9 12 7 2 4 1 12 2 5 2 14 3 10 4 14 10 6 14 10 11 4 14 11 15 11 2 8 11 6 15 6 15 7...
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 555ms
memory: 12948kb
input:
50 30 12 11 47 46 29 28 40 41 29 30 27 28 15 14 1 2 46 45 8 9 16 15 34 33 50 49 45 44 13 14 42 41 35 34 20 19 18 17 48 49 48 47 2 3 23 24 11 10 31 30 40 39 36 35 7 6 23 22 4 3
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 341ms
memory: 12956kb
input:
50 42 24 23 31 30 44 43 9 8 4 5 33 32 41 42 28 27 3 4 18 17 15 14 28 29 2 1 42 43 39 38 6 5 20 21 49 48 25 26 22 23 50 49 9 10 34 35 44 45 31 32 18 19 38 37 36 37 8 7 13 12 27 26 47 46 34 33 24 25 10 11 13 14 12 11 22 21 46 45 20 19 3 2 17 16
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 509ms
memory: 12956kb
input:
50 29 21 20 23 24 21 22 5 4 25 24 28 29 27 26 8 7 1 2 27 28 39 40 32 33 45 44 43 42 47 48 48 49 30 31 38 37 14 15 32 31 38 39 35 34 7 6 46 45 15 16 9 10 36 35 13 12 16 17
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 299ms
memory: 12928kb
input:
50 48 43 44 24 25 35 36 15 14 1 2 46 47 23 22 10 9 46 45 34 33 3 4 12 11 43 42 22 21 40 41 17 16 20 19 32 31 33 32 23 24 6 5 7 8 44 45 16 15 36 37 14 13 39 38 41 42 35 34 48 49 37 38 5 4 29 30 2 3 19 18 13 12 48 47 29 28 9 8 25 26 11 10 27 26 31 30 49 50 39 40 21 20 7 6 28 27
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 302ms
memory: 12872kb
input:
50 48 17 16 22 21 27 28 43 44 30 29 6 7 13 12 50 49 28 29 11 12 21 20 2 3 31 32 43 42 7 8 11 10 19 20 3 4 41 42 8 9 26 27 38 37 5 4 24 25 33 32 23 24 9 10 49 48 19 18 40 41 36 37 45 46 44 45 47 48 39 40 13 14 46 47 34 33 26 25 17 18 14 15 36 35 1 2 15 16 38 39 23 22 5 6 35 34
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 315ms
memory: 12952kb
input:
50 48 30 29 32 30 12 10 20 21 40 39 28 26 4 3 34 36 20 18 4 2 31 30 34 35 46 45 43 44 7 9 43 41 42 40 8 9 49 48 38 36 10 11 28 27 46 47 21 19 6 8 14 13 32 31 6 4 6 7 45 43 37 38 14 16 35 36 12 14 15 17 20 22 25 26 31 33 22 24 5 7 45 47 11 13 23 21 42 43 32 34 29 27 40 41 24 25
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 210ms
memory: 12896kb
input:
50 93 46 44 27 26 1 2 13 11 44 45 18 16 37 35 47 49 19 20 34 33 16 15 23 21 7 6 34 35 28 29 48 46 14 16 6 8 22 20 6 4 30 32 13 14 14 12 4 5 50 49 26 28 31 29 50 48 18 19 19 21 47 46 36 34 11 9 13 12 2 4 8 7 8 9 10 9 17 15 14 15 20 21 3 5 11 12 30 31 43 42 3 4 40 38 1 3 35 36 44 42 48 47 47 45 37 38 ...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 243ms
memory: 12928kb
input:
50 72 20 19 11 12 2 3 11 10 18 19 49 47 25 27 40 41 4 6 26 25 23 21 18 16 33 34 13 15 35 34 17 16 45 44 38 37 44 46 14 13 14 12 28 26 24 26 32 31 49 48 42 41 6 8 43 45 8 10 29 28 24 25 4 5 20 22 39 41 3 1 19 21 23 25 24 22 47 46 33 31 8 7 38 36 37 39 16 15 36 37 12 13 42 43 32 30 35 33 32 34 41 43 4...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 221ms
memory: 12932kb
input:
50 84 16 15 12 14 35 37 24 22 44 42 17 19 30 32 36 38 24 23 36 37 34 36 21 23 33 34 19 20 45 46 22 20 10 12 42 41 25 27 26 27 34 32 15 13 26 25 21 22 7 6 28 30 40 38 1 3 47 49 39 37 29 31 13 14 28 29 35 34 8 6 44 46 30 29 44 45 48 46 33 35 49 50 36 35 11 12 21 19 42 43 7 5 2 1 47 46 33 32 13 12 16 1...
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 216ms
memory: 12948kb
input:
50 92 16 14 20 18 5 4 43 41 36 37 42 40 17 15 13 11 45 47 19 21 23 25 3 2 23 21 14 15 33 34 50 49 21 22 37 39 27 29 40 39 4 3 31 32 1 2 25 24 8 9 50 48 32 30 39 41 33 35 48 49 27 25 26 25 3 1 34 36 45 43 12 10 26 28 22 24 45 46 29 30 10 9 7 5 31 33 46 48 18 16 9 11 42 43 30 28 33 32 45 44 22 23 19 1...
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 190ms
memory: 12896kb
input:
50 128 32 29 19 18 41 43 41 38 21 19 24 22 47 46 37 38 30 27 39 36 17 18 30 33 13 12 44 47 42 45 13 14 26 25 18 20 45 43 3 6 6 4 28 27 15 16 37 35 42 43 42 39 18 16 37 36 37 40 12 14 13 16 35 34 32 31 8 5 38 39 17 19 32 34 2 5 35 32 9 8 26 27 34 36 16 17 12 11 34 31 2 3 25 22 39 40 7 8 34 37 2 4 50 ...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 577ms
memory: 12952kb
input:
50 30 5 6 20 22 28 31 5 7 13 11 32 35 21 18 24 22 17 15 7 8 9 6 36 33 44 43 38 39 2 4 3 2 25 24 40 41 45 44 45 47 50 47 32 29 31 29 23 26 45 46 49 47 19 21 44 41 24 21 47 46
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 197ms
memory: 13008kb
input:
50 114 37 34 2 5 45 47 4 3 42 40 27 24 4 6 27 28 25 24 21 20 31 33 17 16 40 43 30 31 19 16 45 46 4 2 42 41 17 15 13 14 29 28 37 36 35 34 25 22 7 10 6 5 11 8 42 45 22 23 37 40 9 7 38 41 8 7 32 29 3 6 22 19 48 46 25 27 43 46 23 26 38 36 5 7 37 35 33 34 26 24 31 34 18 20 20 19 14 15 42 44 16 18 47 46 1...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 208ms
memory: 12876kb
input:
50 103 5 6 24 25 49 48 8 5 46 44 12 14 5 3 20 19 2 3 17 14 24 22 10 12 25 22 19 18 6 9 26 28 20 17 13 12 40 39 40 38 32 31 36 39 1 3 4 6 42 39 26 25 5 7 35 37 39 41 4 7 31 30 27 30 16 15 11 8 47 45 3 4 35 32 41 40 23 25 24 26 13 10 44 47 42 41 34 35 7 9 8 7 31 34 17 15 35 38 14 16 18 16 16 13 13 15 ...
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 197ms
memory: 12952kb
input:
50 133 18 15 13 16 44 42 35 32 36 34 48 49 17 18 1 4 7 8 3 6 49 47 33 35 22 24 34 35 46 43 27 26 14 12 4 6 42 43 11 14 31 28 40 42 20 18 27 30 30 31 3 5 35 36 18 21 21 24 32 31 40 37 38 35 19 18 22 23 20 22 24 26 40 39 3 4 20 17 4 5 42 45 11 9 4 2 9 10 32 30 11 8 9 12 43 41 38 37 20 23 5 6 46 44 13 ...
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 187ms
memory: 12896kb
input:
50 140 43 40 31 30 45 43 27 29 39 36 28 29 26 23 10 8 24 21 3 7 39 35 47 45 33 35 46 49 46 48 20 24 28 24 27 23 9 8 31 28 36 35 6 2 23 20 30 33 38 42 13 16 44 41 29 32 3 1 8 12 5 7 12 10 7 10 45 49 14 13 30 32 14 10 47 50 24 25 5 2 45 46 36 40 27 28 9 11 15 11 31 35 44 42 34 36 5 3 6 5 42 45 31 34 9...
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 198ms
memory: 12928kb
input:
50 128 3 4 15 14 22 18 33 29 23 24 13 11 45 48 17 20 24 27 21 24 46 44 26 28 8 9 42 39 26 23 43 40 5 7 36 38 36 39 21 17 37 33 28 25 21 19 41 44 27 28 32 31 18 20 36 37 34 35 39 41 5 1 16 14 26 27 11 15 29 28 42 46 12 11 47 44 31 29 48 49 45 49 23 20 12 10 47 50 23 25 31 33 1 3 25 26 38 41 36 40 15 ...
output:
0
result:
ok 1 number(s): "0"
Test #30:
score: 0
Accepted
time: 202ms
memory: 12876kb
input:
50 119 8 7 38 34 10 11 9 10 1 4 28 25 13 11 20 16 50 47 15 12 43 46 25 27 20 21 19 18 5 4 17 15 46 50 2 6 4 6 45 48 44 41 36 38 25 26 23 26 7 5 5 6 10 6 24 23 37 33 22 19 28 27 36 39 10 13 41 45 42 46 13 9 43 42 34 32 16 15 30 31 33 34 8 10 14 15 21 17 32 33 41 37 50 48 6 9 42 38 30 33 32 31 13 15 5...
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 178ms
memory: 12876kb
input:
50 189 11 14 29 28 47 45 49 47 7 11 32 30 33 31 18 17 42 40 23 19 19 20 18 20 24 21 28 27 24 28 16 18 12 8 12 11 41 44 15 18 16 12 13 14 5 3 18 22 34 38 15 16 29 30 20 17 25 23 38 39 48 44 27 31 42 46 36 35 21 20 8 6 32 28 6 7 24 20 32 36 25 24 20 16 6 9 9 7 8 7 36 39 46 48 35 33 41 45 43 41 28 31 5...
output:
1
result:
ok 1 number(s): "1"
Test #32:
score: 0
Accepted
time: 191ms
memory: 12952kb
input:
50 185 12 14 38 40 2 3 15 12 20 24 17 13 22 18 41 42 18 17 1 3 4 6 24 21 20 16 9 10 7 11 41 44 38 41 19 22 7 9 37 38 8 6 24 22 45 44 29 31 48 49 34 33 37 41 10 8 20 17 15 16 14 13 46 42 32 35 39 35 18 21 29 27 47 44 21 22 26 25 47 43 36 33 39 41 11 15 24 25 31 34 11 8 34 38 49 50 33 37 31 33 45 47 1...
output:
0
result:
ok 1 number(s): "0"
Test #33:
score: 0
Accepted
time: 179ms
memory: 12928kb
input:
50 180 35 37 43 44 8 4 24 27 13 9 38 41 34 29 31 28 17 19 41 44 37 33 45 40 9 6 21 17 48 49 3 7 19 20 13 10 17 12 31 35 6 7 7 2 2 3 6 4 31 27 40 35 20 21 6 2 27 23 47 43 21 16 5 4 19 14 28 33 28 32 44 39 47 46 27 22 1 5 17 16 46 48 48 50 44 46 15 18 35 34 13 17 24 20 41 37 24 21 49 45 47 48 5 10 49 ...
output:
1
result:
ok 1 number(s): "1"
Test #34:
score: 0
Accepted
time: 207ms
memory: 12952kb
input:
50 92 39 42 23 27 44 47 12 10 43 45 33 35 46 48 7 11 16 19 15 18 5 6 28 27 35 39 26 21 50 48 44 42 33 38 38 41 3 4 40 37 6 4 23 21 28 24 30 25 7 5 20 22 3 2 43 46 36 37 41 40 34 30 30 27 9 10 34 29 29 26 20 17 6 10 14 16 23 26 6 1 38 39 39 36 8 11 38 37 12 11 9 6 25 27 49 48 17 22 37 39 15 14 22 23 ...
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 180ms
memory: 12948kb
input:
50 222 46 41 44 41 23 19 21 18 19 15 9 11 11 10 36 41 15 11 39 42 23 25 4 1 17 21 40 45 32 33 33 31 24 29 22 23 17 16 32 30 18 17 45 41 12 15 24 27 21 24 26 24 29 27 42 45 6 11 25 24 29 25 18 15 4 3 38 33 47 49 8 5 49 46 21 25 30 25 32 35 45 47 14 13 47 50 19 17 19 16 11 7 38 37 9 4 45 44 35 39 31 3...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 186ms
memory: 12956kb
input:
50 203 36 40 19 16 21 26 20 15 18 14 11 13 28 33 42 45 50 49 26 31 5 6 46 42 41 43 41 36 49 47 19 18 47 44 5 9 26 25 19 17 28 31 2 1 33 34 50 45 21 20 25 22 37 41 13 10 12 14 35 34 22 17 35 31 34 38 23 26 40 42 49 46 22 24 20 23 20 25 40 45 11 7 23 24 8 9 25 29 15 19 14 10 16 17 35 40 38 40 22 27 7 ...
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 178ms
memory: 12952kb
input:
50 203 18 16 45 50 28 24 4 3 28 29 13 18 16 12 25 20 29 30 36 39 44 39 31 28 28 23 40 38 28 26 21 18 40 45 13 15 15 18 49 46 36 41 48 47 16 20 42 47 37 40 24 25 8 10 7 8 3 7 6 5 44 41 48 44 30 34 45 43 16 15 12 17 30 26 19 16 31 36 10 15 42 40 9 10 39 38 49 50 24 27 34 31 34 33 8 5 6 1 35 34 25 27 7...
output:
1
result:
ok 1 number(s): "1"
Test #38:
score: -100
Time Limit Exceeded
input:
50 18 23 27 43 41 31 33 29 30 22 20 25 20 31 27 36 41 30 36 50 49 45 40 25 29 44 49 33 36 14 16 31 29 31 37 35 34