QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882245 | #4273. Good Game | hhoppitree | 0 | 423ms | 71332kb | C++20 | 3.1kb | 2025-02-04 22:40:14 | 2025-02-04 22:40:15 |
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;
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