QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73743 | #4273. Good Game | 12345678 | 0 | 55ms | 42536kb | C++14 | 2.2kb | 2023-01-27 21:11:03 | 2023-01-27 21:11:06 |
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);
}
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 {
}
write((int)Ans.size()), putchar('\n');
for(auto x : Ans) write(x.first), putchar(' '), write(x.second), putchar('\n');
return 0;
}
/*
10
BBABBAABAB
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 2ms
memory: 3524kb
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: 3500kb
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
Wrong Answer
time: 0ms
memory: 3440kb
input:
15 AABABAABABAABAB
output:
0
result:
wrong answer the string has not been fully deleted
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 2ms
memory: 3392kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
0
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 7
Accepted
time: 2ms
memory: 3552kb
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: -7
Wrong Answer
time: 2ms
memory: 3536kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
wrong answer the string has not been fully deleted
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 9
Accepted
time: 55ms
memory: 42536kb
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: -9
Wrong Answer
time: 10ms
memory: 14248kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
0
result:
wrong answer the string has not been fully deleted