QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123803#1444. Palindromeckiseki#AC ✓61ms225156kbC++207.4kb2023-07-13 17:49:052023-07-13 17:49:20

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-13 17:49:20]
  • Judged
  • Verdict: AC
  • Time: 61ms
  • Memory: 225156kb
Show
  • [2023-07-13 17:49:05]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef CKISEKI
#define all(x) begin(x), end(x)
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [";
    while (L != R) cerr << " " << *L++;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

const int maxn = 305;

int dp[maxn][maxn][2][maxn];
int cnt[maxn][2];

void chmin(int &x, int v) {
    x = min(x, v);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;

    for (int i = 0; i < n; i++) {
        cnt[i + 1][0] = cnt[i][0] + (s[i] == '0');
        cnt[i + 1][1] = cnt[i][1] + (s[i] == '1');
    }

    if (cnt[n][0] % 2 == 1 && cnt[n][1] % 2 == 1) {
        cout << -1 << '\n';
        return 0;
    }

    memset(dp, 0x3f, sizeof(dp));

    for (int l = n-1; l >= 0; l--) {
        dp[l][l][0][0] = 0;
        dp[l][l][(s[l] == '1')][s[l] == '0'] = s[l] == '1';
        if (l + 1 < n && s[l] == s[l + 1]) {
            dp[l][l + 1][0][0] = 0;
        }
        for (int r = l; r < n; r++) {
            for (int parity: {0, 1}) {
                for (int x = 0; x <= n; x++) {
                    if (dp[l][r][parity][x] > n) continue;
                    if (l > 0 && r + 1 < n && s[l - 1] == s[r + 1])
                        chmin(dp[l - 1][r + 1][parity][x], dp[l][r][parity][x]);
                    if (l > 0) {
                        chmin(dp[l - 1][r][parity ^ (s[l - 1] == '1')][x + (s[l - 1] == '0')], dp[l][r][parity][x] + (s[l - 1] == '1'));
                    }
                    if (r + 1 < n) {
                        chmin(dp[l][r + 1][parity ^ (s[r + 1] == '1')][x + (s[r + 1] == '0')], dp[l][r][parity][x] + (s[r + 1] == '1'));
                    }
                }
            }
        }
    }

    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            for (int p: {0, 1}) {
                for (int x = 2; x <= n; x++) {
                    chmin(dp[l][r][p][x], dp[l][r][p][x - 2]);
                }
            }
        }
    }

    for (int ans = 0; ans <= n / 2; ans++) {
        int prefix_len = n - ans;

        for (int sep = ans; sep <= prefix_len; sep++) {
            int A = sep - ans;
            int k = ans - A;
            if (k < 0) continue;

            debug(A, k, ans, sep);
            debug(s.substr(sep));
            orange(dp[sep][n-1][0], dp[sep][n-1][0] + n);
            orange(dp[sep][n-1][1], dp[sep][n-1][1] + n);

            for (int x = 0; x <= k; x++) {
                int y = k - x;
                if (ans == 2 && A == 0) {
                    debug(x, y, k, dp[sep][n-1][y % 2][x]);
                }
                if (y >= dp[sep][n - 1][y % 2][x]) {
                    if (x <= cnt[sep][0] && y <= cnt[sep][1] && (x + cnt[sep][0]) % 2 == 0 && (y + cnt[sep][1]) % 2 == 0) {
                        cout << ans << '\n';
                        return 0;
                    }
                }
            }

        }
    }

    cout << (n + 1) / 2 << '\n';

    return 0;
}

/*

   10
1110101010
(A, k, ans, sep) = (0, 0, 0, 0)
(s.substr(sep)) = (1110101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 2 1061109567 0 2 0 2 0 2 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 3 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (0, 1, 1, 1)
(s.substr(sep)) = (110101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 2 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 3 1 3 1 3 1 ]
(A, k, ans, sep) = (1, 0, 1, 2)
(s.substr(sep)) = (10101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (0, 2, 2, 2)
(s.substr(sep)) = (10101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(x, y, k, dp[sep][n-1][y % 2][x]) = (0, 2, 2, 1061109567)
(x, y, k, dp[sep][n-1][y % 2][x]) = (1, 1, 2, 1061109567)
(x, y, k, dp[sep][n-1][y % 2][x]) = (2, 0, 2, 1061109567)
(A, k, ans, sep) = (1, 1, 2, 3)
(s.substr(sep)) = (0101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 ]
(A, k, ans, sep) = (2, 0, 2, 4)
(s.substr(sep)) = (101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (0, 3, 3, 3)
(s.substr(sep)) = (0101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 ]
(A, k, ans, sep) = (1, 2, 3, 4)
(s.substr(sep)) = (101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (2, 1, 3, 5)
(s.substr(sep)) = (01010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 ]
(A, k, ans, sep) = (3, 0, 3, 6)
(s.substr(sep)) = (1010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (0, 4, 4, 4)
(s.substr(sep)) = (101010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (1, 3, 4, 5)
(s.substr(sep)) = (01010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 ]
(A, k, ans, sep) = (2, 2, 4, 6)
(s.substr(sep)) = (1010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 ]
(A, k, ans, sep) = (0, 5, 5, 5)
(s.substr(sep)) = (01010)
[ dp[sep][n-1][0], dp[sep][n-1][0] + n ] = [ 0 1061109567 0 1061109567 0 1061109567 0 1061109567 0 1061109567 ]
[ dp[sep][n-1][1], dp[sep][n-1][1] + n ] = [ 1061109567 1 1061109567 1 1061109567 1 1061109567 1 1061109567 1 ]
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 225108kb

input:

7
1101001

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 19ms
memory: 225068kb

input:

4
1001

output:

0

result:

ok "0"

Test #3:

score: 0
Accepted
time: 8ms
memory: 225104kb

input:

12
110100010011

output:

3

result:

ok "3"

Test #4:

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

input:

19
0010010101110111101

output:

4

result:

ok "4"

Test #5:

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

input:

46
0011000100001111001000010000000001100011101100

output:

8

result:

ok "8"

Test #6:

score: 0
Accepted
time: 7ms
memory: 225064kb

input:

34
0111010110110110011011110001100011

output:

6

result:

ok "6"

Test #7:

score: 0
Accepted
time: 7ms
memory: 225060kb

input:

16
1010000101001010

output:

3

result:

ok "3"

Test #8:

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

input:

50
10101101001100100110111010001001010001011001101011

output:

-1

result:

ok "-1"

Test #9:

score: 0
Accepted
time: 24ms
memory: 225156kb

input:

32
01111001100011100110111111101111

output:

8

result:

ok "8"

Test #10:

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

input:

14
01101101011101

output:

-1

result:

ok "-1"

Test #11:

score: 0
Accepted
time: 8ms
memory: 225104kb

input:

48
101010011000111111001111101111100111110101101101

output:

6

result:

ok "6"

Test #12:

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

input:

29
10111101101100111100110011101

output:

4

result:

ok "4"

Test #13:

score: 0
Accepted
time: 7ms
memory: 225060kb

input:

17
01111001010010101

output:

3

result:

ok "3"

Test #14:

score: 0
Accepted
time: 7ms
memory: 225148kb

input:

134
00100101011101111010001101000111101110011001111110100101010011001010000001011111000000001110101010100010010110111011001011000010110010

output:

18

result:

ok "18"

Test #15:

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

input:

114
001100010000111100100001000000000110001110110001111001100000101100010010110001001001010010111110101000010101111011

output:

-1

result:

ok "-1"

Test #16:

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

input:

97
0111010110110110011011110001100011010110000100111110000011001101011100100010000110010011011100110

output:

18

result:

ok "18"

Test #17:

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

input:

78
101000010100101001100100010110101110110100111000101011111101111010000001101111

output:

-1

result:

ok "-1"

Test #18:

score: 0
Accepted
time: 11ms
memory: 225156kb

input:

61
1010110100110010011011101000100101000101100110101110110000011

output:

8

result:

ok "8"

Test #19:

score: 0
Accepted
time: 16ms
memory: 225072kb

input:

193
0111100110001110011011111110111111111110101001001110101001111101001101101000100010011010000111001101011000110000110101100011110100111001111000000001110000011000011001101011100010111111111001111

output:

32

result:

ok "32"

Test #20:

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

input:

174
011011010111011101100101101111000100011100000111101010011111101001000110001101011001101101001001010001110001000000000111100010111001011110010011000011011001000000010101011000

output:

-1

result:

ok "-1"

Test #21:

score: 0
Accepted
time: 11ms
memory: 225156kb

input:

157
1010100110001111110011111011111001111101011011011010111010101001111101011111010001001101100111011100110000010001011001100010111000100110101110101010001010100

output:

27

result:

ok "27"

Test #22:

score: 0
Accepted
time: 16ms
memory: 225068kb

input:

137
10111101101100111100110011101101101001101100111111101000011001111001010101001001010010001000100001011111000000010101111100011110000000001

output:

25

result:

ok "25"

Test #23:

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

input:

120
011110010100101011000110101010110001111111100000101010010110000001100111101011001001101001000110010001110000001000101110

output:

20

result:

ok "20"

Test #24:

score: 0
Accepted
time: 36ms
memory: 225092kb

input:

255
001001010111011110100011010001111011100110011111101001010100110010100000010111110000000011101010101000100101101110110010110000101100101111000000001111100110000110001010111101011010000100011000110000001101011011100010101010011100101001111011001001101110010

output:

36

result:

ok "36"

Test #25:

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

input:

256
0011000100001111001000010000000001100011101100011110011000001011000100101100010010010100101111101010000101011110110000110110010101011111010110100011110101010000000101011001010010110000011110101110111010100111010010010110010011111100010110111001001010011001

output:

-1

result:

ok "-1"

Test #26:

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

input:

292
0111010110110110011011110001100011010110000100111110000011001101011100100010000110010011011100110011001001101110111100100101010101111110001110010000111111010001011000100010111000100101100110001110000000000101010001010110011010111000101110101100000110000011100100001100100101001010010001001010

output:

-1

result:

ok "-1"

Test #27:

score: 0
Accepted
time: 51ms
memory: 225128kb

input:

294
101000010100101001100100010110101110110100111000101011111101111010000001101111000100000110100101101011100110111110011111111010001100100000010100000010001110100011101111011110101011001101101010110001000111101011111110001010111010110010011100110001001111000101010100111101000011110001111101010010

output:

45

result:

ok "45"

Test #28:

score: 0
Accepted
time: 36ms
memory: 225064kb

input:

229
1010110100110010011011101000100101000101100110101110110000011001110100010100110101001100110100000010110101101111111011110000110001101001011011110011101101101001111110001000100000100010100010011110101111011000111100001110111010111

output:

39

result:

ok "39"

Test #29:

score: 0
Accepted
time: 23ms
memory: 225100kb

input:

231
011110011000111001101111111011111111111010100100111010100111110100110110100010001001101000011100110101100011000011010110001111010011100111100000000111000001100001100110101110001011111111100111111100011000111101011001111100101101011

output:

42

result:

ok "42"

Test #30:

score: 0
Accepted
time: 33ms
memory: 225116kb

input:

233
01101101011101110110010110111100010001110000011110101001111110100100011000110101100110110100100101000111000100000000011110001011100101111001001100001101100100000001010101100000001111110000010100010101001011110101011100110001110000011

output:

33

result:

ok "33"

Test #31:

score: 0
Accepted
time: 46ms
memory: 225096kb

input:

269
10101001100011111100111110111110011111010110110110101110101010011111010111110100010011011001110111001100000100010110011000101110001001101011101010100010101000011001101000010110101010001100011100111011010111001110010001011100010001011011001000110110010111010111100010000

output:

45

result:

ok "45"

Test #32:

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

input:

270
101111011011001111001100111011011010011011001111111010000110011110010101010010010100100010001000010111110000000101011111000111100000000011010101101100001010000010001111101101100111100100100100001101001011001011101000110110010001000100010011001010110010011000011110110110

output:

-1

result:

ok "-1"

Test #33:

score: 0
Accepted
time: 24ms
memory: 225124kb

input:

205
0111100101001010110001101010101100011111111000001010100101100000011001111010110010011010010001100100011100000010001011101011101111010001010001101001011100011001110100001100111001101101010001100001001010000

output:

34

result:

ok "34"

Test #34:

score: 0
Accepted
time: 57ms
memory: 225140kb

input:

299
00100101011101111010001101000111101110011001111110100101010011001010000001011111000000001110101010100010010110111011001011000010110010111100000000111110011000011000101011110101101000010001100011000000110101101110001010101001110010100111101100100110111001001010101101000101100110101001111111010101...

output:

49

result:

ok "49"

Test #35:

score: 0
Accepted
time: 49ms
memory: 225064kb

input:

300
00110001000011110010000100000000011000111011000111100110000010110001001011000100100101001011111010100001010111101100001101100101010111110101101000111101010100000001010110010100101100000111101011101110101001110100100101100100111111000101101110010010100110011100111100111101100111000000011010110000...

output:

50

result:

ok "50"

Test #36:

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

input:

300
01110101101101100110111100011000110101100001001111100000110011010111001000100001100100110111001100110010011011101111001001010101011111100011100100001111110100010110001000101110001001011001100011100000000001010100010101100110101110001011101011000001100000111001000011001001010010100100010010101110...

output:

-1

result:

ok "-1"

Test #37:

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

input:

300
10100001010010100110010001011010111011010011100010101111110111101000000110111100010000011010010110101110011011111001111111101000110010000001010000001000111010001110111101111010101100110110101011000100011110101111111000101011101011001001110011000100111100010101010011110100001111000111110101001011...

output:

-1

result:

ok "-1"

Test #38:

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

input:

300
10101101001100100110111010001001010001011001101011101100000110011101000101001101010011001101000000101101011011111110111100001100011010010110111100111011011010011111100010001000001000101000100111101011110110001111000011101110101110100101010110010010100010010011000000101000011110110111100100010111...

output:

-1

result:

ok "-1"

Test #39:

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

input:

300
01111001100011100110111111101111111111101010010011101010011111010011011010001000100110100001110011010110001100001101011000111101001110011110000000011100000110000110011010111000101111111110011111110001100011110101100111110010110101110111010111100101001101111111000101001001101001111010001001110011...

output:

-1

result:

ok "-1"

Test #40:

score: 0
Accepted
time: 50ms
memory: 225060kb

input:

300
01101101011101110110010110111100010001110000011110101001111110100100011000110101100110110100100101000111000100000000011110001011100101111001001100001101100100000001010101100000001111110000010100010101001011110101011100110001110000011101001001110001010011011011110101110101110100011010001111011010...

output:

44

result:

ok "44"

Test #41:

score: 0
Accepted
time: 52ms
memory: 225128kb

input:

300
10101001100011111100111110111110011111010110110110101110101010011111010111110100010011011001110111001100000100010110011000101110001001101011101010100010101000011001101000010110101010001100011100111011010111001110010001011100010001011011001000110110010111010111100010000001000100111101101110001100...

output:

48

result:

ok "48"

Test #42:

score: 0
Accepted
time: 61ms
memory: 225116kb

input:

299
10111101101100111100110011101101101001101100111111101000011001111001010101001001010010001000100001011111000000010101111100011110000000001101010110110000101000001000111110110110011110010010010000110100101100101110100011011001000100010001001100101011001001100001111011011000011001011100101011100001...

output:

54

result:

ok "54"

Test #43:

score: 0
Accepted
time: 54ms
memory: 225124kb

input:

299
01111001010010101100011010101011000111111110000010101001011000000110011110101100100110100100011001000111000000100010111010111011110100010100011010010111000110011101000011001110011011010100011000010010100000010000001110011101001101110001100101111101010111001100101001100100001100100000000000110101...

output:

51

result:

ok "51"

Test #44:

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

input:

1
1

output:

0

result:

ok "0"

Test #45:

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

input:

1
0

output:

0

result:

ok "0"

Test #46:

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

input:

2
10

output:

-1

result:

ok "-1"

Test #47:

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

input:

2
11

output:

0

result:

ok "0"

Test #48:

score: 0
Accepted
time: 7ms
memory: 225088kb

input:

3
111

output:

0

result:

ok "0"

Test #49:

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

input:

5
10000

output:

3

result:

ok "3"

Test #50:

score: 0
Accepted
time: 12ms
memory: 225068kb

input:

9
000000001

output:

4

result:

ok "4"

Test #51:

score: 0
Accepted
time: 8ms
memory: 225132kb

input:

5
11100

output:

3

result:

ok "3"
English 繁體中文 简体中文

Server Time: 2025-04-11 21:52:06 | OpenSource Project