QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424627#3223. Cellular Automatonalpha1022WA 0ms3864kbC++141.6kb2024-05-29 14:34:012024-05-29 14:34:01

Judging History

你现在查看的是最新测评结果

  • [2024-05-29 14:34:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3864kb
  • [2024-05-29 14:34:01]
  • 提交

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'