QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72944 | #4273. Good Game | SSL_TJH | 0 | 4ms | 9204kb | C++14 | 2.8kb | 2023-01-20 21:30:11 | 2023-01-20 21:30:12 |
Judging History
answer
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6 + 100;
int n, m, ls[N], rs[N], a[N], Ls[N], Rs[N];
char s[N];
vector <pair<int, int> > ans;
bool shit;
void write() {
if (shit) {printf("-1"); return ;}
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
}
void clean(int l, int sz) {
if (sz & 1) ans.push_back(make_pair(l, 3)), sz -= 3;
while (sz) ans.push_back(make_pair(l, 2)), sz -= 2;
}
void lnk_clean(int x, int y) {
clean(ls[x], rs[x] - ls[x] + 1 + ((x ^ y) ? rs[y] - ls[y] + 1 : 0));
}
void work() {
if (shit) return ;
int k = (m + 1) / 2;
if (a[k] == 2) {
int clsz = 0;
for (int i = 1; i <= k; i++) {
int l = k - i + 1, r = k + i - 1;
clean(ls[l], rs[r] - ls[l] + 1 - clsz);
clsz = rs[r] - ls[l] + 1;
}
return ;
}
int lc = -1, rc = -1;
for (int i = k - 1; i >= 1; i--) if (a[i] == 2) {lc = i; break;}
for (int i = k + 1; i <= m; i++) if (a[i] == 2) {rc = i; break;}
if (lc == -1 || rc == -1) {shit = 1; return ;}
int dis = min(k - lc + 1, rc - k + 1);
if (k - lc > rc - k) {
for (int i = 1; i <= dis; i++) lnk_clean(rc - i + 1, rc + i - 1);
int tmp = rs[rc + dis - 1] - ls[rc - dis + 1] + 1;
for (int i = rc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
m -= dis * 2;
}
else {
for (int i = 1; i <= dis; i++) lnk_clean(lc - i + 1, lc + i - 1);
int tmp = rs[lc + dis - 1] - ls[lc - dis + 1] + 1;
for (int i = lc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
m -= dis * 2;
}
k = (m + 1) / 2;
int clsz = 0;
for (int i = 1; i <= k; i++) {
int l = k - i + 1, r = k + i - 1;
clean(ls[l], rs[r] - ls[l] + 1 - clsz);
clsz = rs[r] - ls[l] + 1;
}
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int L = 1, R; L <= n; L = R + 1) {
R = L; while (R < n && s[R + 1] == s[R]) R++;
m++; ls[m] = L; rs[m] = R; if (L != R) a[m] = 2; else a[m] = 1;
}
int num = 0;
for (int i = 1; i <= m; i++) {
if (a[i] == 2) Ls[i] = Ls[i - 1], num = 0;
else {
num++; Ls[i] = max(Ls[i - 1], num);
}
}
num = 0;
for (int i = m; i >= 1; i--) {
if (a[i] == 2) Rs[i] = Rs[i + 1], num = 0;
else {
num++; Rs[i] = max(Rs[i + 1], num);
}
}
if (m & 1) {work(); write(); return 0;}
int bk = -1;
for (int i = 1; i <= m; i += 2)
if ((a[(i + 1) / 2] == 2 || Ls[i] < i / 2) && (a[(m + i + 1) / 2] == 2 || Rs[i + 1] < (m - i) / 2)) {
bk = i; break;
}
if (bk == -1) shit = 1;
int tmp = m, tmp_d = rs[bk];
m = bk; work(); m = tmp;
for (int i = bk + 1; i <= m; i++) ls[i - bk] = ls[i] - tmp_d, rs[i - bk] = rs[i] - tmp_d, a[i - bk] = a[i];
m = m - bk; work(); m = tmp;
write();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 3
Accepted
time: 1ms
memory: 9128kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: -3
Time Limit Exceeded
input:
13 ABABBABABBABA
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #51:
score: 6
Accepted
time: 4ms
memory: 9088kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
-1
result:
ok no solution
Test #52:
score: 0
Accepted
time: 3ms
memory: 9204kb
input:
300 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...
output:
-1
result:
ok no solution
Test #53:
score: -6
Time Limit Exceeded
input:
299 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #102:
score: 0
Time Limit Exceeded
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #153:
score: 0
Time Limit Exceeded
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...