QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882248 | #4273. Good Game | hhoppitree | 0 | 421ms | 71336kb | C++20 | 3.1kb | 2025-02-04 22:41:53 | 2025-02-04 22:41:53 |
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 - 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;
}
詳細信息
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