QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424628#3223. Cellular Automatonalpha1022AC ✓1ms3960kbC++141.6kb2024-05-29 14:34:252024-05-29 14:34:26

Judging History

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

  • [2024-05-29 14:34:26]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3960kb
  • [2024-05-29 14:34:25]
  • 提交

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'