QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#882248#4273. Good Gamehhoppitree0 421ms71336kbC++203.1kb2025-02-04 22:41:532025-02-04 22:41:53

Judging History

This is the latest submission verdict.

  • [2025-02-04 22:41:53]
  • Judged
  • Verdict: 0
  • Time: 421ms
  • Memory: 71336kb
  • [2025-02-04 22:41:53]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, m, pre[N], nxt[N], sum[N];
vector< pair<int, int> > p;

int get(int x) {
    int tx = x, s = 0;
    for (; x; x -= x & -x) s += sum[x];
    for (x = tx; x <= n; x += x & -x) --sum[x];
    return s;
}

set<int> S;
vector< pair<int, int> > res;

void del(int l, int r) {
    l = p[l].first, r = p[r].second;
    vector<int> arr;
    for (auto it = S.lower_bound(l); it != S.end() && *it <= r; ++it) {
        arr.push_back(*it);
    }
    for (auto x : arr) S.erase(x);
    while (arr.size() >= 5 || arr.size() == 3) {
        res.push_back({get(arr.end()[-3]), 3});
        get(arr.end()[-2]), get(arr.end()[-1]);
        arr.erase(arr.end() - 3, arr.end());
    }
    while (arr.size() >= 2) {
        res.push_back({get(arr.end()[-2]), 2});
        get(arr.end()[-1]);
        arr.erase(arr.end() - 2, arr.end());
    }
}

void solve(int l, int r) {
    if (p[(l + r) / 2].first != p[(l + r) / 2].second) {
        for (int tl = (l + r) / 2, tr = (l + r) / 2; tl >= l && tr <= r; --tl, ++tr) {
            del(tl, tr);
        }
    } else {
        int fi = (l + r) / 2, se = (l + r) / 2;
        while (p[fi].first == p[fi].second) --fi;
        while (p[se].first == p[se].second) ++se;
        vector<int> z;
        for (int i = 1; i <= se - (l + r) / 2; ++i) {
            del(fi - i + 1, fi + i - 1);
        }
        for (int i = l; i <= fi - (se - (l + r) / 2); ++i) z.push_back(i);
        for (int i = fi + (se - (l + r) / 2) + 1; i <= r; ++i) z.push_back(i);
        for (int tl = z.size() / 2, tr = z.size() / 2; tl >= 0 && tr < (int)z.size(); --tl, ++tr) {
            del(z[tl], z[tr]);
        }
    }
}

signed main() {
    scanf("%d", &n);
    string str; cin >> str;
    int lst = 1;
    for (int i = 0; i <= n; ++i) {
        if (i == n || (i != 0 && str[i] != str[i - 1])) p.push_back({lst, i}), lst = i + 1;
    }
    m = p.size();
    for (int i = 0, len = 0; i < m; ++i) {
        if (p[i].first == p[i].second) ++len;
        else len = 0;
        pre[i] = len;
        if (i) pre[i] = max(pre[i], pre[i - 1]);
    }
    for (int i = m - 1, len = 0; ~i; --i) {
        if (p[i].first == p[i].second) ++len;
        else len = 0;
        nxt[i] = len;
        if (i != m - 1) nxt[i] = max(nxt[i], nxt[i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        ++sum[i];
        if (i + (i & -i) <= n) sum[i + (i & -i)] += sum[i];
        S.insert(i);
    }
    if (m & 1) {
        if (p[m / 2].first != p[m / 2].second || pre[m - 1] < m / 2) {
            solve(0, m - 1);
        }
    } else {
        for (int i = 0; i < m; i += 2) {
            if ((p[i / 2].first != p[i / 2].second || pre[i] < i / 2) && (p[(i + m) / 2].first != p[(i + m) / 2].second || pre[i + 1] < (m - i - 2) / 2)) {
                solve(0, i), solve(i + 1, m - 1);
                break;
            }
        }
    }
    if (res.empty()) return 0 & puts("-1");
    printf("%d\n", (int)res.size());
    for (auto [x, y] : res) printf("%d %d\n", x, y);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

9
ABAABBBAA

output:

4
3 2
4 2
2 2
1 3

result:

ok good solution!

Test #2:

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

input:

13
ABABBABABBABA

output:

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

result:

ok good solution!

Test #3:

score: 3
Accepted
time: 1ms
memory: 8016kb

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: 3
Accepted
time: 0ms
memory: 8016kb

input:

15
ABAABBBABAABBAB

output:

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

result:

ok good solution!

Test #5:

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

input:

1
B

output:

-1

result:

ok no solution

Test #6:

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

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

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

input:

7
AAAABBB

output:

3
3 2
1 2
1 3

result:

ok good solution!

Test #8:

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

input:

11
BBBBBBAAAAA

output:

4
4 3
1 3
3 3
1 2

result:

ok good solution!

Test #9:

score: 3
Accepted
time: 1ms
memory: 8016kb

input:

2
AB

output:

-1

result:

ok no solution

Test #10:

score: 3
Accepted
time: 1ms
memory: 8020kb

input:

14
BAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #11:

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

input:

14
ABBABAABBABBAB

output:

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

result:

ok good solution!

Test #12:

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

input:

15
BAABABABBABBAAB

output:

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

result:

ok good solution!

Test #13:

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

input:

14
BABBBBBBBBBBAB

output:

6
10 3
7 3
5 2
3 2
2 2
1 2

result:

ok good solution!

Test #14:

score: 3
Accepted
time: 1ms
memory: 8012kb

input:

15
BABAAAAAAAAABAB

output:

6
10 3
7 3
4 3
3 2
2 2
1 2

result:

ok good solution!

Test #15:

score: 3
Accepted
time: 1ms
memory: 8016kb

input:

14
BBBABAAAAAAABA

output:

6
1 3
7 3
5 2
3 2
2 2
1 2

result:

ok good solution!

Test #16:

score: 3
Accepted
time: 1ms
memory: 8016kb

input:

15
AAAABABAAAAABAB

output:

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

result:

ok good solution!

Test #17:

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

input:

14
BAAABABAAAABAB

output:

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

result:

ok good solution!

Test #18:

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

input:

15
ABAAAABABBBBABA

output:

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

result:

ok good solution!

Test #19:

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

input:

14
BABAAABAAAABAB

output:

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

result:

ok good solution!

Test #20:

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

input:

15
BABBABABBBBBBAB

output:

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

result:

ok good solution!

Test #21:

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

input:

14
BABAAAABABBBAB

output:

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

result:

ok good solution!

Test #22:

score: 3
Accepted
time: 1ms
memory: 8012kb

input:

15
BABAAAAAABABAAB

output:

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

result:

ok good solution!

Test #23:

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

input:

14
BABBBBBABAAAAA

output:

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

result:

ok good solution!

Test #24:

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

input:

15
BABAAAABABAAAAA

output:

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

result:

ok good solution!

Test #25:

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

input:

15
BAABABAABAABBAA

output:

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

result:

ok good solution!

Test #26:

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

input:

15
AABAABBAABAABAB

output:

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

result:

ok good solution!

Test #27:

score: 3
Accepted
time: 1ms
memory: 8016kb

input:

15
AABABBABAABBABB

output:

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

result:

ok good solution!

Test #28:

score: 3
Accepted
time: 1ms
memory: 8020kb

input:

15
BAABBABBAABABBA

output:

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

result:

ok good solution!

Test #29:

score: 0
Wrong Answer
time: 0ms
memory: 8016kb

input:

15
BBAABBABABABBAA

output:

5
1 2
3 2
1 3
5 2
4 3

result:

wrong answer wrong solution (expected NO SOLUTION)

Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 0ms
memory: 8148kb

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

101
34 2
33 3
32 3
31 3
30 3
29 3
28 3
29 2
27 2
26 3
25 3
24 3
23 3
22 3
21 3
20 3
19 3
18 3
17 3
16 3
15 3
14 3
13 3
12 3
11 3
10 3
9 3
8 3
7 3
6 3
5 3
4 3
3 3
2 3
1 3
130 2
128 3
126 3
124 3
122 3
120 3
118 3
116 3
114 3
112 3
110 3
108 3
106 3
104 3
102 3
100 3
99 2
97 2
95 3
93 3
91 3
89 3
87 3...

result:

wrong answer wrong solution (expected NO SOLUTION)

Subtask #3:

score: 0
Wrong Answer

Test #102:

score: 7
Accepted
time: 1ms
memory: 8268kb

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2997
1998 2
1996 2
1995 2
1994 2
1993 2
1992 2
1991 2
1990 2
1989 2
1988 2
1987 2
1986 2
1985 2
1984 2
1983 2
1982 2
1981 2
1980 2
1979 2
1978 2
1977 2
1976 2
1975 2
1974 2
1973 2
1972 2
1971 2
1970 2
1969 2
1968 2
1967 2
1966 2
1965 2
1964 2
1963 2
1962 2
1961 2
1960 2
1959 2
1958 2
1957 2
1956 2
1...

result:

ok good solution!

Test #103:

score: 7
Accepted
time: 1ms
memory: 8400kb

input:

5999
BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
3 3
1 2
1998 2
1996 2
1995 2
1994 2
1993 2
1992 2
1991 2
1990 2
1989 2
1988 2
1987 2
1986 2
1985 2
1984 2
1983 2
1982 2
1981 2
1980 2
1979 2
1978 2
1977 2
1976 2
1975 2
1974 2
1973 2
1972 2
1971 2
1970 2
1969 2
1968 2
1967 2
1966 2
1965 2
1964 2
1963 2
1962 2
1961 2
1960 2
1959 2
1958 2
1957 2
...

result:

ok good solution!

Test #104:

score: 7
Accepted
time: 2ms
memory: 8228kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
1499 3
1498 3
1497 2
1496 2
1495 2
1494 2
1493 2
1492 2
1491 2
1490 2
1489 2
1488 2
1487 2
1486 2
1485 2
1484 2
1483 2
1482 2
1481 2
1480 2
1479 2
1478 2
1477 2
1476 2
1475 2
1474 2
1473 2
1472 2
1471 2
1470 2
1469 2
1468 2
1467 2
1466 2
1465 2
1464 2
1463 2
1462 2
1461 2
1460 2
1459 2
1458 2
1...

result:

ok good solution!

Test #105:

score: 0
Wrong Answer
time: 0ms
memory: 8268kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2400
1198 3
1197 3
1196 2
1195 2
1194 2
1193 2
1192 2
1191 2
1190 2
1189 2
1188 2
1187 2
1186 2
1185 2
1184 2
1183 2
1182 2
1181 2
1180 2
1179 2
1178 2
1177 2
1176 2
1175 2
1174 2
1173 2
1172 2
1171 2
1170 2
1169 2
1168 2
1167 2
1166 2
1165 2
1164 2
1163 2
1162 2
1161 2
1160 2
1159 2
1158 2
1157 2
1...

result:

wrong answer invalid operation on step #1199: BA

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 9
Accepted
time: 421ms
memory: 71300kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499996
333331 3
333328 3
333327 2
333326 2
333325 2
333324 2
333323 2
333322 2
333321 2
333320 2
333319 2
333318 2
333317 2
333316 2
333315 2
333314 2
333313 2
333312 2
333311 2
333310 2
333309 2
333308 2
333307 2
333306 2
333305 2
333304 2
333303 2
333302 2
333301 2
333300 2
333299 2
333298 2
33329...

result:

ok good solution!

Test #154:

score: 9
Accepted
time: 419ms
memory: 71260kb

input:

999998
BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499996
4 3
1 3
333331 3
333328 3
333327 2
333326 2
333325 2
333324 2
333323 2
333322 2
333321 2
333320 2
333319 2
333318 2
333317 2
333316 2
333315 2
333314 2
333313 2
333312 2
333311 2
333310 2
333309 2
333308 2
333307 2
333306 2
333305 2
333304 2
333303 2
333302 2
333301 2
333300 2
333299 2
333298...

result:

ok good solution!

Test #155:

score: 9
Accepted
time: 420ms
memory: 71308kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
249999 2
250000 2
249998 2
249997 2
249996 2
249995 2
249994 2
249993 2
249992 2
249991 2
249990 2
249989 2
249988 2
249987 2
249986 2
249985 2
249984 2
249983 2
249982 2
249981 2
249980 2
249979 2
249978 2
249977 2
249976 2
249975 2
249974 2
249973 2
249972 2
249971 2
249970 2
249969 2
24996...

result:

ok good solution!

Test #156:

score: 0
Wrong Answer
time: 391ms
memory: 71336kb

input:

999998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

400000
199998 3
199997 3
199996 2
199995 2
199994 2
199993 2
199992 2
199991 2
199990 2
199989 2
199988 2
199987 2
199986 2
199985 2
199984 2
199983 2
199982 2
199981 2
199980 2
199979 2
199978 2
199977 2
199976 2
199975 2
199974 2
199973 2
199972 2
199971 2
199970 2
199969 2
199968 2
199967 2
19996...

result:

wrong answer invalid operation on step #199999: BA