QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882245#4273. Good Gamehhoppitree0 423ms71332kbC++203.1kb2025-02-04 22:40:142025-02-04 22:40:15

Judging History

This is the latest submission verdict.

  • [2025-02-04 22:40:15]
  • Judged
  • Verdict: 0
  • Time: 423ms
  • Memory: 71332kb
  • [2025-02-04 22:40:14]
  • 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);
                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;
}

詳細信息

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: 0
Wrong Answer
time: 0ms
memory: 8012kb

input:

15
AABABAABABAABAB

output:

5
1 2
4 2
3 2
5 3
4 2

result:

wrong answer invalid operation on step #4: AAB

Subtask #2:

score: 0
Wrong Answer

Test #51:

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

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

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: 0
Wrong Answer
time: 3ms
memory: 8268kb

input:

5999
BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2996
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:

wrong answer invalid operation on step #1002: BBA

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 9
Accepted
time: 423ms
memory: 71264kb

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: 0
Wrong Answer
time: 417ms
memory: 71332kb

input:

999998
BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499994
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:

wrong answer invalid operation on step #166668: BBA