QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#772486 | #3223. Cellular Automaton | lyxeason | WA | 0ms | 3976kb | C++14 | 1.7kb | 2024-11-22 19:48:56 | 2024-11-22 19:48:57 |
Judging History
answer
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int W;
struct Edge {
int u;
int v;
int w;
} G[209];
struct Ed {
int v;
int w;
};
vector<Ed> E[69];
int N;
char s[209];
bool A[209];
queue<int> q;
bool in[69];
int dis[69];
bool Chk () {
int t;
while (!q.empty()) q.pop();
memset(in, 0, sizeof(in));
memset(dis, 0x3f, sizeof(dis));
dis[0] = 0, q.push(0);
in[0] = true;
while (!q.empty()) {
t = q.front(), q.pop();
in[t] = false;
for (Ed v : E[t])
if (dis[v.v] > dis[t] + v.w) {
dis[v.v] = dis[t] + v.w;
if (!in[v.v]) q.push(v.v), in[v.v] = true;
}
if (dis[0] < 0) return false;
}
return true;
}
int main () {
scanf("%d%s", &W, s);
N = (1 << (2 * W + 1));
for (int i = 0; i < N; i++) A[i] = s[i] - '0';
for (int i = 0; i < (1 << (2 * W)); i++) G[i] = {i, i >> 1, 0}, G[(i | (1 << (2 * W)))] = {i, (i | (1 << (2 * W))) >> 1, 1};
for (int i = N - 1; i >= 0; i--)
if (!A[i]) {
A[i] ^= 1;
for (int j = 0; j < (1 << (2 * W)); j++) E[j].clear();
for (int j = 0; j < N; j++)
if (j <= i) E[G[j].u].push_back({G[j].v, G[j].w - A[j]}), E[G[j].v].push_back({G[j].u, A[j] - G[j].w});
else E[G[j].u].push_back({G[j].v, G[j].w}), E[G[j].v].push_back({G[j].u, G[j].w ^ 1});
if (Chk()) {
for (int j = 0; j < N; j++) putchar(dis[G[j].u] + G[j].w - dis[G[j].v] + '0');
puts("");
return 0;
}
A[i] ^= 1;
}
puts("no");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3964kb
input:
1 11111111
output:
no
result:
ok single line: 'no'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 11111101
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 11001011
output:
no
result:
ok single line: 'no'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
1 10111110
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 10000010
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 00100011
output:
00110011
result:
ok single line: '00110011'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 01000001
output:
01000111
result:
ok single line: '01000111'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
1 00000100
output:
00001111
result:
ok single line: '00001111'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 01001000
output:
01010101
result:
ok single line: '01010101'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1 00001000
output:
00001111
result:
ok single line: '00001111'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
1 00000000
output:
00001111
result:
ok single line: '00001111'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
2 11111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 11111111001111111111111111111110
output:
no
result:
ok single line: 'no'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
2 11111011011111001110111011011101
output:
no
result:
ok single line: 'no'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
2 11011101110111101111111101110111
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 11011011111000101011001101110011
output:
no
result:
ok single line: 'no'
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3976kb
input:
2 00010000010001100111101111101110
output:
00010000010100111101111101010011
result:
wrong answer 1st lines differ - expected: '00010000010100001101111101011111', found: '00010000010100111101111101010011'