QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648309#3223. Cellular AutomatonDSCS2009AC ✓5ms3780kbC++142.0kb2024-10-17 18:15:392024-10-17 18:15:40

Judging History

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

  • [2024-10-17 18:15:40]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:3780kb
  • [2024-10-17 18:15:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int v, w;
    Edge(int v, int w) : v(v), w(w) {}
};

const int N = 150, M = N * N;
int w, dis[N], cnt[N], vis[N], q[M];
string s, ans;
vector<Edge> G[N];

bool spfa() {
    memset(dis, 0x3f, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    int l = 0, r = -1;
    dis[0] = 0, vis[0] = true, q[++r] = 0;
    while (l <= r) {
        int u = q[l++];
        vis[u] = false;
        for (const Edge& e : G[u]) {
            if (dis[e.v] > dis[u] + e.w) {
                dis[e.v] = dis[u] + e.w;
                cnt[e.v] = cnt[u] + 1;
                if (cnt[e.v] > (1 << (w + w + 1)) + 3) return false;
                if (!vis[e.v]) q[++r] = e.v, vis[e.v] = true;
            }
        }
    }
    return true;
}

#define bin(x) bitset<16>(x).to_string().c_str()

#define shift(x, y) ((x) << 1 & ((1 << (w + w + 1)) - 1) | ((y) & 1))

bool check() {
    for (int i = 0; i < N; i++) G[i].clear();
    for (int i = 0; i < (1 << (w + w + 1)); i++) {
        int u = shift(i, 0), v = shift(i, 1);
        int top_b = i >> (w + w) & 1;
        G[u].emplace_back(v, 0);
        G[v].emplace_back(u, 0);
        int l = 0, r = 1;
        if (i < ans.size()) {
            if (ans[i] == '0') r = 0;
            else l = 1;
        }
        G[i].emplace_back(u, top_b - l);
        G[u].emplace_back(i, r - top_b);
    }
    return spfa();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> w >> s;
    ans = s;
    if (check()) {
        cout << ans << endl;
        return 0;
    }
    for (int i = s.size() - 1; i >= 0; i--)
        if (s[i] == '0') {
            ans = s.substr(0, i);
            ans.push_back('1');
            if (check()) {
                while (ans.size() < s.size()) {
                    ans.push_back('0');
                    if (!check()) ans.back() = '1';
                }
                cout << ans << endl;
                return 0;
            }
        }
    cout << "no" << endl;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3736kb

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: 3664kb

input:

1
11001011

output:

no

result:

ok single line: 'no'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

1
10111110

output:

no

result:

ok single line: 'no'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3760kb

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: 3740kb

input:

1
01000001

output:

01000111

result:

ok single line: '01000111'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1
00000100

output:

00001111

result:

ok single line: '00001111'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1
01001000

output:

01010101

result:

ok single line: '01010101'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1
00001000

output:

00001111

result:

ok single line: '00001111'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

1
00000000

output:

00001111

result:

ok single line: '00001111'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2
11111111111111111111111111111111

output:

no

result:

ok single line: 'no'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

2
11111111001111111111111111111110

output:

no

result:

ok single line: 'no'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2
11111011011111001110111011011101

output:

no

result:

ok single line: 'no'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

2
11011101110111101111111101110111

output:

no

result:

ok single line: 'no'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2
11011011111000101011001101110011

output:

no

result:

ok single line: 'no'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

2
00010000010001100111101111101110

output:

00010000010100001101111101011111

result:

ok single line: '00010000010100001101111101011111'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

2
01001010101010011010011000111001

output:

01010000010100000101111101011111

result:

ok single line: '01010000010100000101111101011111'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2
10001110000000000000010000100001

output:

no

result:

ok single line: 'no'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

2
00100010010010010000001000000101

output:

00100011000000000010111111111111

result:

ok single line: '00100011000000000010111111111111'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

2
00100000000001000000100000000000

output:

00100000000011110010110011111111

result:

ok single line: '00100000000011110010110011111111'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2
00000000000000000000000000000000

output:

00000000000000001111111111111111

result:

ok single line: '00000000000000001111111111111111'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

3
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

output:

no

result:

ok single line: 'no'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

3
10101011111111111111111111111111110111111111110011111111111111101111111110111101111111111111111100111111101111101011111110111111

output:

no

result:

ok single line: 'no'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3660kb

input:

3
11111100111111101101111111111110111110111111111110101101010111111111111011011111111101110111011101111111010011111111111011011111

output:

no

result:

ok single line: 'no'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

3
10111110011110010111101011101011111000100110111111001111111011110110010111111001111101010010110000101111111010111111111111011001

output:

no

result:

ok single line: 'no'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3724kb

input:

3
11101110111001011110110100001111010111000000010010011001011100111111110011100010011010011011111111010011111110000111010111011100

output:

no

result:

ok single line: 'no'

Test #28:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

3
10101111000011010011010111111011000100100001101000001011111011101000110101011001110110011010001101111010011101111000011111111101

output:

no

result:

ok single line: 'no'

Test #29:

score: 0
Accepted
time: 4ms
memory: 3656kb

input:

3
00000000000010000000110001000001011101000011001001000001011101000011010000000001000101000000100101100001010011111100001111100000

output:

00000000000010000000110100000000000000100000100000001111111111111111111111111011000011011111000000000010111110111111111111111111

result:

ok single line: '000000000000100000001101000000...0000010111110111111111111111111'

Test #30:

score: 0
Accepted
time: 5ms
memory: 3720kb

input:

3
01000000110100111100001000001001000011100000010101110100001000000010010000110100000001100110001010010000001100000000000001011100

output:

01000001000000000000000000000000000100010000001101010001000000000111110111111111111111111111111111011101111111110101000111111111

result:

ok single line: '010000010000000000000000000000...1011101111111110101000111111111'

Test #31:

score: 0
Accepted
time: 5ms
memory: 3732kb

input:

3
00100010001000100000000000000001100000100000000100000000001010100100000000001000110000000000000000101000000000000000010000000000

output:

00100010001000100000000000000011000001000000000000101100011011110010111011101110000011001111111111110111111111111110111101101111

result:

ok single line: '001000100010001000000000000000...1110111111111111110111101101111'

Test #32:

score: 0
Accepted
time: 4ms
memory: 3716kb

input:

3
00100000000100000010000000010101000000000100000000001100000000000000000000000100100000000001000000000000000000010000010000001000

output:

00100000000100000010000011111111000000000101000000101111011111110010110000010000111011110000000011111111010111111110111101111111

result:

ok single line: '001000000001000000100000111111...1111111010111111110111101111111'

Test #33:

score: 0
Accepted
time: 3ms
memory: 3768kb

input:

3
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111

result:

ok single line: '000000000000000000000000000000...1111111111111111111111111111111'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1
00011101

output:

00011101

result:

ok single line: '00011101'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

1
00011000

output:

00011101

result:

ok single line: '00011101'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

1
11111111

output:

no

result:

ok single line: 'no'