QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73110 | #4273. Good Game | FISHER_ | 0 | 63ms | 33840kb | C++14 | 2.2kb | 2023-01-22 11:19:41 | 2023-01-22 11:19:43 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int maxn = 1000000;
char str[maxn + 5];
vector<pair<int, int>> op;
#define mid (s.size() >> 1)
void print0(int st, int c) {
if (c & 1) op.emplace_back(st, 3), c -= 3;
while (c) op.emplace_back(st, 2), c -= 2;
}
void print1(const vector<pair<int, int>>& s) {
int sum = 0;
for (int i = 0; i < mid; i++) sum += s[i].se;
print0(sum + 1, s[mid].se);
for (int i = 1; i <= mid; i++) {
sum -= s[mid - i].se;
print0(sum + 1, s[mid - i].se + s[mid + i].se);
}
}
void print2(const vector<pair<int, int>>& s) {
int l, r;
for (l = mid; !s[l].fi; l--) ;
for (r = mid; !s[r].fi; r++) ;
int sum = 0;
for (int i = 0; i < l; i++) sum += s[i].se;
print0(sum + 1, s[l].se);
for (int i = 1; i < r - mid; i++) {
sum -= s[l - i].se;
print0(sum + 1, s[l - i].se + s[l + i].se);
}
vector<pair<int, int>> lft(s.begin(), s.begin() + l - r + mid);
lft.emplace_back(1, s[l - r + mid].se + s[l + r - mid].se);
lft.insert(lft.end(), s.begin() + l + r - mid + 1, s.end());
print1(lft);
}
bool ok[maxn + 5];
int main() {
int n;
scanf("%d%s", &n, str + 1);
vector<pair<int, int>> s;
for (int l = 1, r; l <= n; l = r + 1) {
for (r = l; r < n && str[r + 1] == str[l]; r++) ;
s.emplace_back(r > l, r - l + 1);
}
if (s.size() % 2 == 1) {
if (s[mid].fi) print1(s);
else {
int mx = 0, nw = 0;
for (const auto& x : s) mx = max(mx, nw = x.fi ? nw + 1 : 0);
if (mx < mid) print2(s);
else return printf("-1"), 0;
}
} else {
int mx = 0, nw = 0;
for (int i = s.size() - 1; ~i; i--) {
mx = max(mx, nw = s[i].fi ? nw + 1 : 0);
if (i & 1) ok[i] = mx < (s.size() - i) / 2 || s[(s.size() + i) / 2].fi;
}
mx = nw = 0;
for (int i = 0; i < s.size(); i++) {
mx = max(mx, nw = s[i].fi ? nw + 1 : 0);
if (i & 1 ^ 1 && ok[i + 1] && (mx < i / 2 || s[i / 2].fi)) {
vector<pair<int, int>> s1(s.begin(), s.begin() + i + 1), s2(s.begin() + i + 1, s.end());
s[i / 2].fi ? print1(s1) : print2(s1);
s[(s.size() + i) / 2].fi ? print1(s2) : print2(s2);
goto ed;
}
}
return printf("-1"), 0;
}
ed: printf("%zu\n", op.size());
for (const auto& p : op) printf("%d %d\n", p.fi, p.se);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 3
Accepted
time: 2ms
memory: 3588kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 2ms
memory: 3624kb
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
Accepted
time: 2ms
memory: 3596kb
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: 0
Accepted
time: 2ms
memory: 3644kb
input:
15 ABAABBBABAABBAB
output:
7 3 2 2 2 2 2 1 2 4 2 2 3 1 2
result:
ok good solution!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 B
output:
-1
result:
ok no solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
2 BB
output:
1 1 2
result:
ok good solution!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
7 AAAABBB
output:
3 1 2 1 2 1 3
result:
ok good solution!
Test #8:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
11 BBBBBBAAAAA
output:
5 1 2 1 2 1 2 1 3 1 2
result:
ok good solution!
Test #9:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
2 AB
output:
-1
result:
ok no solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
14 BAAAAAAAAAAAAA
output:
-1
result:
ok no solution
Test #11:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
14 ABBABAABBABBAB
output:
7 2 2 1 2 4 2 5 2 2 2 2 2 1 2
result:
ok good solution!
Test #12:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
15 BAABABABBABBAAB
output:
6 2 2 6 2 5 2 4 3 3 3 1 3
result:
ok good solution!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
14 BABBBBBBBBBBAB
output:
7 3 2 3 2 3 2 3 2 3 2 2 2 1 2
result:
ok good solution!
Test #14:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
15 BABAAAAAAAAABAB
output:
7 4 3 4 2 4 2 4 2 3 2 2 2 1 2
result:
ok good solution!
Test #15:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
14 BBBABAAAAAAABA
output:
6 1 3 3 3 3 2 3 2 2 2 1 2
result:
ok good solution!
Test #16:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
15 AAAABABAAAAABAB
output:
7 1 2 1 2 4 3 4 2 3 2 2 2 1 2
result:
ok good solution!
Test #17:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
14 BAAABABAAAABAB
output:
6 2 3 5 2 5 2 4 2 3 2 1 3
result:
ok good solution!
Test #18:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
15 ABAAAABABBBBABA
output:
7 3 2 3 2 5 2 5 2 4 2 2 3 1 2
result:
ok good solution!
Test #19:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
14 BABAAABAAAABAB
output:
6 4 3 5 2 5 2 3 3 2 2 1 2
result:
ok good solution!
Test #20:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
15 BABBABABBBBBBAB
output:
7 3 2 2 2 4 2 4 2 4 2 3 2 1 3
result:
ok good solution!
Test #21:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
14 BABAAAABABBBAB
output:
6 4 2 4 2 3 2 4 3 2 3 1 2
result:
ok good solution!
Test #22:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
15 BABAAAAAABABAAB
output:
7 4 2 4 2 4 2 3 2 2 2 3 2 1 3
result:
ok good solution!
Test #23:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
14 BABBBBBABAAAAA
output:
6 3 3 3 2 2 2 1 2 1 3 1 2
result:
ok good solution!
Test #24:
score: -3
Memory Limit Exceeded
input:
15 BABAAAABABAAAAA
output:
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #51:
score: 0
Memory Limit Exceeded
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
result:
Subtask #3:
score: 0
Memory Limit Exceeded
Test #102:
score: 7
Accepted
time: 3ms
memory: 3776kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1996 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
Accepted
time: 2ms
memory: 3824kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1 3 1 2 1996 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
Memory Limit Exceeded
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
result:
Subtask #4:
score: 0
Memory Limit Exceeded
Test #153:
score: 9
Accepted
time: 61ms
memory: 24936kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333328 2 333328 2 333328 2 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 33329...
result:
ok good solution!
Test #154:
score: 0
Accepted
time: 63ms
memory: 33840kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 1 2 1 2 1 2 333328 2 333328 2 333328 2 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 33...
result:
ok good solution!
Test #155:
score: -9
Memory Limit Exceeded
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...