QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424627 | #3223. Cellular Automaton | alpha1022 | WA | 0ms | 3864kb | C++14 | 1.6kb | 2024-05-29 14:34:01 | 2024-05-29 14:34:01 |
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("-1"); 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: 0
Wrong Answer
time: 0ms
memory: 3864kb
input:
1 11111111
output:
-1
result:
wrong answer 1st lines differ - expected: 'no', found: '-1'