QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882222 | #4273. Good Game | hhoppitree | 0 | 430ms | 71404kb | C++20 | 2.9kb | 2025-02-04 22:23:00 | 2025-02-04 22:23:00 |
Judging History
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