QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684431 | #7303. City United | Afterlife | WA | 76ms | 9936kb | C++20 | 1.7kb | 2024-10-28 13:24:07 | 2024-10-28 13:24:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n , m;
vector<int> E[55];
const int N = 1.6e6;
short f[2][N] ;
int pw[15];
void upd(short &x,short y) {
((x += y) &= 3) ;
}
int work(int x) {
if(x >= pw[13]) x -= pw[13];
if(x >= pw[13]) x -= pw[13];
return x;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
cin >> n >> m;
pw[0] = 1;
for(int i = 1;i <= 14;i++) pw[i] = 3 * pw[i - 1];
for(int i = 1;i <= m;i++) {
int u , v;
cin >> u >> v;
if(u > v) swap(u , v);
E[v].push_back(u) ;
}
f[0][0] = 1;
int cur = 0;
for(int i = 0;i < n;i++) {
for(int j = 0;j < pw[min(i + 1 , 13)] ; j++) f[cur ^ 1][j] = 0;
for(int j = 0;j < pw[min(i , 13)] ;j++) {
int g[13] = {0} , t = j;
for(int k = 0;k < 12;k++) {
g[k] = t % 3 ; t /= 3;
}
for(int d = 0;d < 3;d++) {
if(d == 2) upd(f[cur ^ 1][work(j * 3 + 2)] , f[cur][j]) ;
else {
bool ff = 1;
for(auto v : E[i + 1]) {
if(g[i - v] == 1 - d) {ff = 0 ; break ;}
}
if(ff) upd(f[cur ^ 1][work(j * 3 + d)] , f[cur][j]) ;
}
}
// printf("%d : ",i) ;
// for(int k = 0;k < min(i , 13);k++) printf("%d ",g[k]) ;
// printf(" : %d\n",f[cur][j]) ;
}
cur ^= 1;
}
short ans = 3;
for(int j = 0;j < pw[min(n , 13)] ; j++) {
// ans += f[cur][j];
upd(ans , f[cur][j]) ;
}
// cout << ans << '\n';
if(ans == 2) cout << 1 << '\n';
else cout << 0 << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5668kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 74ms
memory: 9876kb
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: 76ms
memory: 9788kb
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: 70ms
memory: 9816kb
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: 66ms
memory: 9868kb
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: 71ms
memory: 9868kb
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: 73ms
memory: 9792kb
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: 66ms
memory: 9780kb
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: 70ms
memory: 9848kb
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: -100
Wrong Answer
time: 76ms
memory: 9936kb
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:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'