QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882222#4273. Good Gamehhoppitree0 430ms71404kbC++202.9kb2025-02-04 22:23:002025-02-04 22:23:00

Judging History

This is the latest submission verdict.

  • [2025-02-04 22:23:00]
  • Judged
  • Verdict: 0
  • Time: 430ms
  • Memory: 71404kb
  • [2025-02-04 22:23:00]
  • 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;
        for (int i = 1; i <= se - (l + r) / 2; ++i) {
            del(fi - i + 1, fi + i - 1);
        }
        del(se, se);
        for (int tl = fi - (se - (l + r) / 2), tr = se + 1; tl >= l && tr <= r; --tl, ++tr) {
            del(tl, tr);
        }
    }
}

signed main() {
    scanf("%d", &n);
    string str; cin >> str;
    int lst = 1;
    for (int i = 0; i < n; ++i) {
        if (i == n - 1 || (i != 0 && str[i] != str[i - 1])) p.push_back({lst, i + 1}), 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: 0
Wrong Answer
time: 0ms
memory: 7888kb

input:

9
ABAABBBAA

output:

4
3 3
4 2
2 2
1 2

result:

wrong answer invalid operation on step #1: AAB

Subtask #2:

score: 0
Wrong Answer

Test #51:

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

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

133
165 3
165 2
163 2
163 2
161 2
161 2
159 2
159 2
157 2
157 2
155 2
155 2
153 2
153 2
151 2
151 2
149 2
149 2
147 2
147 2
145 2
145 2
143 2
143 2
141 2
141 2
139 2
139 2
137 2
137 2
135 2
135 2
133 2
133 3
131 2
131 2
129 2
129 2
127 2
127 2
125 2
125 2
123 2
123 2
121 2
121 2
119 2
119 2
117 2
11...

result:

wrong answer wrong solution (expected NO SOLUTION)

Subtask #3:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 1ms
memory: 8084kb

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2997
1 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2957 2
2956 2
2955 2
2954...

result:

wrong answer invalid operation on step #1: BA

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 0
Wrong Answer
time: 430ms
memory: 71404kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499996
1 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
499967 2
499966 2
499965 2
499964 2
4...

result:

wrong answer invalid operation on step #1: AB