QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73744 | #4273. Good Game | 12345678 | 0 | 85ms | 57984kb | C++14 | 2.9kb | 2023-01-27 21:21:32 | 2023-01-27 21:21:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
const int mod = 1e9 + 7;
inline int read () {
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar ();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ();
return x * f;
}
inline void write (int x) {
if (x < 0) x = -x, putchar ('-');
if (x >= 10) write (x / 10);
putchar (x % 10 + '0');
}
int n;
char ch[1000005];
int tot;
vector <pii> Ans;
vector <int> a;
int f[1000005][3], pre[1000005][3];
void print0(int fr, int x) {
if(x & 1) Ans.push_back(mp(fr, 3)), x -= 3;
while(x >= 2) Ans.push_back(mp(fr, 2)), x -= 2;
}
void print1(vector <int> bas) {
int mid = (int)bas.size() / 2, rk = 0;
for(int i = 0; i < mid; i++) rk += bas[i];
print0(rk + 1, bas[mid]);
for(int i = 1; i <= mid; i++) {
rk -= bas[mid-i];
print0(rk + 1, bas[mid-i] + bas[mid+i]);
}
}
void print2(vector <int> bas) {
int mid = (int)bas.size() / 2, rk = 0;
int l = mid, r = mid;
while(bas[l] < 2) l--;
while(bas[r] < 2) r++;
for(int i = 0; i < l; i++) rk += bas[i];
print0(rk + 1, bas[l]);
for(int i = 1; i < r - mid; i++) {
rk -= bas[l-i];
print0(rk + 1, bas[l-i] + bas[l+i]);
}
vector <int> lst(bas.begin(), bas.begin() + l - r + mid);
lst.push_back(bas[l-r+mid] + bas[l+r-mid]);
lst.insert(lst.end(), bas.begin() + l + r - mid + 1, bas.end());
print1(lst);
}
int tag[1000005];
signed main () {
// freopen (".in", "r", stdin);
// freopen (".out", "w", stdout);
n = read();
scanf("%s", ch + 1);
a.push_back(1);
for(int i = 2; i <= n; i++) {
if(ch[i] != ch[i-1]) a.push_back(1);
else a.back()++;
}
tot = (int)a.size();
if(tot & 1) {
if(a[tot/2] >= 2) print1(a);
else {
int mx = 0, s = 0;
for(auto x : a) {
if(x < 2) s++;
else s = 0;
mx = max(mx, s);
}
if(mx < tot / 2) print2(a);
else return printf("-1\n") & 0;
}
}
else {
int mx = 0, s = 0;
for(int i = (int)a.size() - 1; i >= 0; i--) {
if(a[i] < 2) s++;
else s = 0;
mx = max(mx, s);
if(i & 1) tag[i] = (mx < ((int)a.size() - i) / 2 || a[((int)a.size()+i)/2] >= 2);
}
mx = 0, s = 0;
for(int i = 0; i < (int)a.size(); i++) {
if(a[i] < 2) s++;
else s = 0;
mx = max(mx, s);
if(!(i & 1) && tag[i+1] && (mx < i / 2 || a[i/2] >= 2)) {
vector<int> s1(a.begin(), a.begin() + i + 1), s2(a.begin() + i + 1, a.end());
if(s1[(int)s1.size()/2] >= 2) print1(s1);
else print2(s1);
if(s2[(int)s2.size()/2] >= 2) print1(s2);
else print2(s2);
break;
}
if(i == (int)a.size() - 1) return printf("-1\n") & 1;
}
}
write((int)Ans.size()), putchar('\n');
for(auto x : Ans) write(x.first), putchar(' '), write(x.second), putchar('\n');
return 0;
}
/*
10
BBABBAABAB
*/
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 3
Accepted
time: 0ms
memory: 3432kb
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: 3556kb
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: 3384kb
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: 3436kb
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: 1ms
memory: 3500kb
input:
1 B
output:
-1
result:
ok no solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
2 BB
output:
1 1 2
result:
ok good solution!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
7 AAAABBB
output:
3 1 2 1 2 1 3
result:
ok good solution!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
11 BBBBBBAAAAA
output:
5 1 2 1 2 1 2 1 3 1 2
result:
ok good solution!
Test #9:
score: -3
Runtime Error
input:
2 AB
output:
-1
result:
Subtask #2:
score: 0
Runtime Error
Test #51:
score: 0
Runtime Error
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
Subtask #3:
score: 0
Runtime Error
Test #102:
score: 7
Accepted
time: 2ms
memory: 3548kb
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: 3596kb
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: 0
Accepted
time: 2ms
memory: 3648kb
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
Accepted
time: 3ms
memory: 3668kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2999 1201 2 1198 2 1198 2 1197 2 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 1...
result:
ok good solution!
Test #106:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
5999 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2999 1199 2 1198 2 1197 2 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 1...
result:
ok good solution!
Test #107:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 1998 2 1997 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 1...
result:
ok good solution!
Test #108:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
5997 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
2998 1 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2...
result:
ok good solution!
Test #109:
score: -7
Runtime Error
input:
6000 ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
-1
result:
Subtask #4:
score: 0
Runtime Error
Test #153:
score: 9
Accepted
time: 63ms
memory: 42420kb
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: 78ms
memory: 57984kb
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: 0
Accepted
time: 85ms
memory: 43880kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499998 249999 2 249998 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
Accepted
time: 58ms
memory: 46640kb
input:
999998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 200001 2 199998 2 199998 2 199997 2 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 19996...
result:
ok good solution!
Test #157:
score: 0
Accepted
time: 65ms
memory: 46664kb
input:
999999 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499999 199999 2 199999 2 199998 2 199997 2 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 19996...
result:
ok good solution!
Test #158:
score: 0
Accepted
time: 66ms
memory: 45120kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499998 333331 2 333330 2 333329 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 33329...
result:
ok good solution!
Test #159:
score: 0
Accepted
time: 17ms
memory: 12340kb
input:
999999 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
499999 1 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1...
result:
ok good solution!
Test #160:
score: -9
Runtime Error
input:
999998 BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1