QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121623#4273. Good Gamebashkort#3 10ms4200kbC++202.6kb2023-07-08 15:48:072024-07-04 00:31:23

Judging History

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

  • [2024-07-04 00:31:23]
  • 评测
  • 测评结果：3
  • 用时：10ms
  • 内存：4200kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-08 15:48:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector dp(n, vector<int>(n));

    for (int l = n - 1; l >= 0; --l) {
        for (int r = l + 1; r < n; ++r) {
            if (r <= l + 2 && s[l] == s[r] && s[l] == s[l + r >> 1]) {
                dp[l][r] = -1;
            } else {
                for (int mid = l + 1, cnt = 0; mid + 1 < r && ++cnt <= 100; ++mid) {
                    if (dp[l][mid] && dp[mid + 1][r]) {
                        dp[l][r] = mid;
                        break;
                    }
                }
                for (int mid = r - 1, cnt = 0; mid >= l && ++cnt <= 100; --mid) {
                    if (dp[l][mid] && dp[mid + 1][r]) {
                        dp[l][r] = mid;
                        break;
                    }
                }
                if (!dp[l][r] && s[l] == s[r]) {
                    for (int mid = l + 1, cnt = 0; mid < r && cnt < 1000; ++mid) {
                        if (s[mid] == s[l] && (l + 1 > mid - 1 ? true : dp[l + 1][mid - 1]) && (mid + 1 > r - 1 ? true : dp[mid + 1][r - 1])) {
                            dp[l][r] = ~mid;
                            break;
                        }
                        cnt += s[mid] == s[l];
                    }
                    if (dp[l + 1][r - 1]) {
                        dp[l][r] = r;
                    }
                }
            }
        }
    }

    if (!dp[0][n - 1]) {
        cout << "-1\n";
        return 0;
    }

    vector<pair<int, int>> ans;

    auto dfs = [&](auto dfs, int l, int r, int del) -> int {
        if (l > r) {
            return 0;
        }
        if (l + 2 >= r) {
            ans.push_back({l - del, r - l + 1});
            return r - l + 1;
        }
        if (dp[l][r] >= 0) {
            int mid = dp[l][r];
            if (mid < r) {
                del += dfs(dfs, l, mid, del);
                dfs(dfs, mid + 1, r, del);
            } else {
                dfs(dfs, l + 1, r - 1, del);
                ans.push_back({l - del, 2});
            }
        } else {
            int mid = ~dp[l][r];
            int d = del;
            del += dfs(dfs, l + 1, mid - 1, del);
            del += dfs(dfs, mid + 1, r - 1, del);
            ans.push_back({l - d, 3});
        }
        return r - l + 1;
    };

    dfs(dfs, 0, n - 1, 0);

    cout << size(ans) << '\n';

    for (auto [l, r] : ans) {
        cout << l + 1 << " " << r << '\n';
    }

    return 0;
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

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

input:

9
ABAABBBAA

output:

4
3 2
2 2
2 2
1 3

result:

ok good solution!

Test #2:

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

input:

13
ABABBABABBABA

output:

6
4 2
3 2
5 2
4 2
2 3
1 2

result:

ok good solution!

Test #3:

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

input:

15
AABABAABABAABAB

output:

7
1 2
4 2
3 2
5 2
4 2
2 3
1 2

result:

ok good solution!

Test #4:

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

input:

15
ABAABBBABAABBAB

output:

7
3 2
2 2
2 2
1 2
4 2
2 3
1 2

result:

ok good solution!

Test #5:

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

input:

1
B

output:

-1

result:

ok no solution

Test #6:

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

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

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

input:

7
AAAABBB

output:

3
1 2
1 2
1 3

result:

ok good solution!

Test #8:

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

input:

11
BBBBBBAAAAA

output:

5
1 2
1 2
1 2
1 3
1 2

result:

ok good solution!

Test #9:

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

input:

2
AB

output:

-1

result:

ok no solution

Test #10:

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

input:

14
BAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #11:

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

input:

14
ABBABAABBABBAB

output:

7
2 2
1 2
2 2
1 2
3 2
2 2
1 2

result:

ok good solution!

Test #12:

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

input:

15
BAABABABBABBAAB

output:

6
2 2
6 2
5 2
4 3
3 3
1 3

result:

ok good solution!

Test #13:

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

input:

14
BABBBBBBBBBBAB

output:

7
3 2
3 2
3 2
3 2
3 2
2 2
1 2

result:

ok good solution!

Test #14:

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

input:

15
BABAAAAAAAAABAB

output:

7
4 3
4 2
4 2
4 2
3 2
2 2
1 2

result:

ok good solution!

Test #15:

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

input:

14
BBBABAAAAAAABA

output:

6
1 3
3 3
3 2
3 2
2 2
1 2

result:

ok good solution!

Test #16:

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

input:

15
AAAABABAAAAABAB

output:

7
1 2
1 2
4 3
4 2
3 2
2 2
1 2

result:

ok good solution!

Test #17:

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

input:

14
BAAABABAAAABAB

output:

6
2 3
5 2
5 2
4 2
3 2
1 3

result:

ok good solution!

Test #18:

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

input:

15
ABAAAABABBBBABA

output:

7
3 2
3 2
5 2
5 2
4 2
2 3
1 2

result:

ok good solution!

Test #19:

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

input:

14
BABAAABAAAABAB

output:

6
4 3
5 2
5 2
3 3
2 2
1 2

result:

ok good solution!

Test #20:

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

input:

15
BABBABABBBBBBAB

output:

7
3 2
2 2
4 2
4 2
4 2
3 2
1 3

result:

ok good solution!

Test #21:

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

input:

14
BABAAAABABBBAB

output:

6
4 2
4 2
3 2
4 3
2 3
1 2

result:

ok good solution!

Test #22:

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

input:

15
BABAAAAAABABAAB

output:

7
4 2
4 2
4 2
3 2
2 2
3 2
1 3

result:

ok good solution!

Test #23:

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

input:

14
BABBBBBABAAAAA

output:

6
3 3
3 2
2 2
1 2
1 3
1 2

result:

ok good solution!

Test #24:

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

input:

15
BABAAAABABAAAAA

output:

7
4 2
4 2
3 2
2 2
1 2
1 3
1 2

result:

ok good solution!

Test #25:

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

input:

15
BAABABAABAABBAA

output:

7
2 2
1 2
3 2
2 2
1 3
1 2
1 2

result:

ok good solution!

Test #26:

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

input:

15
AABAABBAABAABAB

output:

7
1 2
2 2
1 2
5 2
4 2
2 3
1 2

result:

ok good solution!

Test #27:

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

input:

15
AABABBABAABBABB

output:

7
5 2
4 2
3 2
1 3
2 2
1 2
1 2

result:

ok good solution!

Test #28:

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

input:

15
BAABBABBAABABBA

output:

7
4 2
2 3
1 2
2 2
1 2
2 2
1 2

result:

ok good solution!

Test #29:

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

input:

15
BBAABBABABABBAA

output:

-1

result:

ok no solution

Test #30:

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

input:

15
ABABBAABBAABBAB

output:

-1

result:

ok no solution

Test #31:

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

input:

14
AAABAAAAABAAAB

output:

5
1 3
2 3
2 2
3 3
1 3

result:

ok good solution!

Test #32:

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

input:

15
ABBBBABBBBBABBB

output:

6
2 2
2 2
3 3
3 2
1 3
1 3

result:

ok good solution!

Test #33:

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

input:

14
BBBBABBABAAABA

output:

6
1 2
1 2
2 2
4 3
3 2
1 3

result:

ok good solution!

Test #34:

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

input:

15
AAAAABABBBABBAB

output:

6
1 3
1 2
3 3
4 2
2 3
1 2

result:

ok good solution!

Test #35:

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

input:

14
AABABBBBABAAAB

output:

6
1 2
3 2
3 2
2 2
3 3
1 3

result:

ok good solution!

Test #36:

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

input:

15
BAABAAAABABBBBA

output:

7
2 2
3 2
3 2
1 3
2 2
2 2
1 2

result:

ok good solution!

Test #37:

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

input:

14
ABBBABAAABAAAB

output:

5
2 3
1 2
2 3
3 3
1 3

result:

ok good solution!

Test #38:

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

input:

15
BAAABABBBBABAAA

output:

6
2 3
4 2
4 2
3 2
1 3
1 3

result:

ok good solution!

Test #39:

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

input:

14
BABBABBBBABAAA

output:

6
3 2
4 2
4 2
2 3
1 2
1 3

result:

ok good solution!

Test #40:

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

input:

15
ABAAABABBBABBBB

output:

6
3 3
2 2
3 3
1 3
1 2
1 2

result:

ok good solution!

Test #41:

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

input:

14
AABABABBAABBAA

output:

-1

result:

ok no solution

Test #42:

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

input:

15
AABBBABABAABBAA

output:

-1

result:

ok no solution

Test #43:

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

input:

14
AABBAABABABBAA

output:

-1

result:

ok no solution

Test #44:

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

input:

15
BBBAABBAABABABB

output:

-1

result:

ok no solution

Test #45:

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

input:

15
BABABBBBAABBAAA

output:

-1

result:

ok no solution

Test #46:

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

input:

15
BBBABABAABBBAAA

output:

-1

result:

ok no solution

Test #47:

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

input:

15
AAABBBBAABABABB

output:

-1

result:

ok no solution

Test #48:

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

input:

15
AAAAABBAABBABAB

output:

-1

result:

ok no solution

Test #49:

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

input:

15
BAAAABBAABBBABA

output:

-1

result:

ok no solution

Test #50:

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

input:

15
BABAAABBBAAABBA

output:

-1

result:

ok no solution

Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 6
Accepted
time: 3ms
memory: 3748kb

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #52:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #53:

score: 0
Accepted
time: 10ms
memory: 3984kb

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

149
96 2
96 2
96 2
96 2
95 2
94 2
93 2
92 2
91 2
90 2
89 2
88 2
87 2
86 2
85 2
84 2
83 2
82 2
81 2
80 2
79 2
78 2
77 2
76 2
75 2
74 2
73 2
72 2
71 2
70 2
69 2
68 2
67 2
66 2
65 2
64 2
63 2
62 2
61 2
60 2
59 2
58 2
57 2
56 2
55 2
54 2
53 2
52 2
51 2
50 2
49 2
97 2
97 2
97 2
96 2
95 2
94 2
93 2
92 2
9...

result:

ok good solution!

Test #54:

score: 0
Accepted
time: 6ms
memory: 4200kb

input:

299
BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

148
1 2
1 2
1 2
96 3
95 2
94 2
93 2
92 2
91 2
90 2
89 2
88 2
87 2
86 2
85 2
84 2
83 2
82 2
81 2
80 2
79 2
78 2
77 2
76 2
75 2
74 2
73 2
72 2
71 2
70 2
69 2
68 2
67 2
66 2
65 2
64 2
63 2
62 2
61 2
60 2
59 2
58 2
57 2
56 2
55 2
54 2
53 2
52 2
51 2
50 2
49 2
97 3
97 2
96 2
95 2
94 2
93 2
92 2
91 2
90 2...

result:

ok good solution!

Test #55:

score: -6
Wrong Answer
time: 9ms
memory: 3720kb

input:

297
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

-1

result:

wrong answer you didn't find a solution but jury did

Subtask #3:

score: 0
Time Limit Exceeded

Test #102:

score: 0
Time Limit Exceeded

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

result:

Subtask #4:

score: 0
Time Limit Exceeded

Test #153:

score: 0
Time Limit Exceeded

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2025-01-20 21:14:39 | 開源專案