QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424628 | #3223. Cellular Automaton | alpha1022 | AC ✓ | 1ms | 3960kb | C++14 | 1.6kb | 2024-05-29 14:34:25 | 2024-05-29 14:34:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int K = 5;
int n, m;
vector<pair<int, int>> e[1 << (K * 2 + 2)];
int dis[1 << (K * 2 + 2)], c[1 << (K * 2 + 2)];
bool check(string s) {
fill_n(e, m * 2, vector<pair<int, int>>());
for (int i = 0; i < m; ++i)
for (int j = 0; j < 2; ++j) {
int k = ((i << 1) | j) & (m - 1);
if (k < s.size()) {
int w = j - (s[k] ^ '0');
e[i].emplace_back(k, w), e[k].emplace_back(i, -w);
} else e[i].emplace_back(k + m, j), e[k + m].emplace_back(i, -j);
}
for (int i = s.size(); i < m; ++i) e[i + m].emplace_back(i, 0), e[i].emplace_back(i + m, 1);
fill_n(dis, m * 2, inf), fill_n(c, m * 2, 0);
deque<int> q; dis[0] = 0, q.push_back(0);
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (auto [v, w] : e[u])
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!v || (c[v] = c[u] + 1) > m * 2 - (int)s.size()) return 0;
if (q.empty() || dis[v] > dis[q.front()]) q.push_back(v);
else q.push_front(v);
}
}
return 1;
}
void solve() {
cin >> n, m = 1 << (n * 2 + 1);
string s; cin >> s;
if (check(s)) cout << s << "\n";
else {
int pos = -1;
for (int i = m; i--; )
if (s[i] == '0' && check(s.substr(0, i) + "1")) {
pos = i; break;
}
if (pos == -1) { puts("no"); return ; }
auto ans = s.substr(0, pos) + "1";
for (int i = pos + 1; i < m; ++i) {
ans += "0";
if (!check(ans)) ans.back() = '1';
}
cout << ans << " \n";
}
}
int T;
int main() {
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
input:
1 11111111
output:
no
result:
ok single line: 'no'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
1 11111101
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 11001011
output:
no
result:
ok single line: 'no'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 10111110
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
1 10000010
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 00100011
output:
00110011
result:
ok single line: '00110011 '
Test #7:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
1 01000001
output:
01000111
result:
ok single line: '01000111 '
Test #8:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 00000100
output:
00001111
result:
ok single line: '00001111 '
Test #9:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1 01001000
output:
01010101
result:
ok single line: '01010101 '
Test #10:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 00001000
output:
00001111
result:
ok single line: '00001111 '
Test #11:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 00000000
output:
00001111
result:
ok single line: '00001111 '
Test #12:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
2 11111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2 11111111001111111111111111111110
output:
no
result:
ok single line: 'no'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 11111011011111001110111011011101
output:
no
result:
ok single line: 'no'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 11011101110111101111111101110111
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2 11011011111000101011001101110011
output:
no
result:
ok single line: 'no'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
2 00010000010001100111101111101110
output:
00010000010100001101111101011111
result:
ok single line: '00010000010100001101111101011111 '
Test #18:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 01001010101010011010011000111001
output:
01010000010100000101111101011111
result:
ok single line: '01010000010100000101111101011111 '
Test #19:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2 10001110000000000000010000100001
output:
no
result:
ok single line: 'no'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 00100010010010010000001000000101
output:
00100011000000000010111111111111
result:
ok single line: '00100011000000000010111111111111 '
Test #21:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
2 00100000000001000000100000000000
output:
00100000000011110010110011111111
result:
ok single line: '00100000000011110010110011111111 '
Test #22:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
2 00000000000000000000000000000000
output:
00000000000000001111111111111111
result:
ok single line: '00000000000000001111111111111111 '
Test #23:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
3 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
3 10101011111111111111111111111111110111111111110011111111111111101111111110111101111111111111111100111111101111101011111110111111
output:
no
result:
ok single line: 'no'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
3 11111100111111101101111111111110111110111111111110101101010111111111111011011111111101110111011101111111010011111111111011011111
output:
no
result:
ok single line: 'no'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
3 10111110011110010111101011101011111000100110111111001111111011110110010111111001111101010010110000101111111010111111111111011001
output:
no
result:
ok single line: 'no'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
3 11101110111001011110110100001111010111000000010010011001011100111111110011100010011010011011111111010011111110000111010111011100
output:
no
result:
ok single line: 'no'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 10101111000011010011010111111011000100100001101000001011111011101000110101011001110110011010001101111010011101111000011111111101
output:
no
result:
ok single line: 'no'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
3 00000000000010000000110001000001011101000011001001000001011101000011010000000001000101000000100101100001010011111100001111100000
output:
00000000000010000000110100000000000000100000100000001111111111111111111111111011000011011111000000000010111110111111111111111111
result:
ok single line: '000000000000100000001101000000...000010111110111111111111111111 '
Test #30:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
3 01000000110100111100001000001001000011100000010101110100001000000010010000110100000001100110001010010000001100000000000001011100
output:
01000001000000000000000000000000000100010000001101010001000000000111110111111111111111111111111111011101111111110101000111111111
result:
ok single line: '010000010000000000000000000000...011101111111110101000111111111 '
Test #31:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
3 00100010001000100000000000000001100000100000000100000000001010100100000000001000110000000000000000101000000000000000010000000000
output:
00100010001000100000000000000011000001000000000000101100011011110010111011101110000011001111111111110111111111111110111101101111
result:
ok single line: '001000100010001000000000000000...110111111111111110111101101111 '
Test #32:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 00100000000100000010000000010101000000000100000000001100000000000000000000000100100000000001000000000000000000010000010000001000
output:
00100000000100000010000011111111000000000101000000101111011111110010110000010000111011110000000011111111010111111110111101111111
result:
ok single line: '001000000001000000100000111111...111111010111111110111101111111 '
Test #33:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
3 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
result:
ok single line: '000000000000000000000000000000...111111111111111111111111111111 '
Test #34:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1 00011101
output:
00011101
result:
ok single line: '00011101'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1 00011000
output:
00011101
result:
ok single line: '00011101 '
Test #36:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1 11111111
output:
no
result:
ok single line: 'no'