QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334779 | #4273. Good Game | Max_s_xaM | 0 | 42ms | 25616kb | C++14 | 3.9kb | 2024-02-22 13:34:22 | 2024-02-22 13:34:23 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 1e6 + 10;
int n, m, a[MAXN], pos[MAXN];
char s[MAXN];
int pre[MAXN], suf[MAXN];
vector < pair <int, int> > res;
inline void Delete(int pos, int len)
{
if (len & 1) res.emplace_back(pos, 3), len -= 3;
for (int i = 1; i <= len / 2; i++)
res.emplace_back(pos, 2);
}
inline void Solve(int l, int r)
{
int mid = l + r >> 1, lpos = mid, rpos = mid;
while (a[lpos] == 1) lpos--;
while (a[rpos] == 1) rpos++;
int p = lpos + 1;
for (int i = 1; i <= rpos - mid; i++)
{
Delete(pos[lpos], a[lpos]);
a[--lpos]++, p++;
}
pos[p] = pos[lpos] + a[lpos];
for (int i = p + 1; i <= r; i++) pos[i] = pos[i - 1] + a[i - 1];
Delete(pos[rpos], a[rpos]);
int lp = rpos - 1, rp = rpos + 1;
while (rp <= r)
{
if (lp == p - 1) lp = lpos;
Delete(pos[lp], a[lp] + a[rp]);
lp--, rp++;
}
}
inline void Print()
{
cout << res.size() << '\n';
for (auto x : res) cout << x.first << ' ' << x.second << '\n';
}
int main()
{
// freopen("C.in", "r", stdin);
// freopen("C.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(s + 1);
pos[0] = 1;
for (int i = 1, cnt = 0; i <= n + 1; i++)
{
if (i != 1 && s[i] != s[i - 1]) a[++m] = cnt, pos[m] = pos[m - 1] + a[m - 1], cnt = 1;
else cnt++;
}
for (int i = 1; i <= m; i++) pre[i] = (a[i] == 1 ? pre[i - 1] + 1 : 0);
for (int i = m; i >= 1; i--) suf[i] = (a[i] == 1 ? suf[i + 1] + 1 : 0);
if (m & 1)
{
int mid = m + 1 >> 1;
if (pre[mid] + suf[mid] >= mid) cout << "-1\n";
else Solve(1, m), Print();
return 0;
}
for (int i = 1; i <= m; i += 2)
{
int lmid = i + 1 >> 1, rmid = i + m + 1 >> 1;
if (pre[lmid] + suf[lmid] < lmid && pre[rmid] + suf[rmid] < rmid)
{
Solve(i + 1, m), Solve(1, i), Print();
return 0;
}
}
cout << "-1\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 0ms
memory: 9840kb
input:
9 ABAABBBAA
output:
4 3 2 2 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 1ms
memory: 9736kb
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: 1ms
memory: 9744kb
input:
15 AABABAABABAABAB
output:
7 6 2 5 2 7 2 6 2 4 3 3 2 1 2
result:
ok good solution!
Test #4:
score: 0
Accepted
time: 2ms
memory: 11776kb
input:
15 ABAABBBABAABBAB
output:
7 12 2 10 3 9 2 3 2 2 2 2 2 1 2
result:
ok good solution!
Test #5:
score: 0
Accepted
time: 0ms
memory: 9776kb
input:
1 B
output:
-1
result:
ok no solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 13932kb
input:
2 BB
output:
1 1 2
result:
ok good solution!
Test #7:
score: 0
Accepted
time: 2ms
memory: 13796kb
input:
7 AAAABBB
output:
3 5 3 1 2 1 2
result:
ok good solution!
Test #8:
score: 0
Accepted
time: 2ms
memory: 11772kb
input:
11 BBBBBBAAAAA
output:
5 7 3 7 2 1 2 1 2 1 2
result:
ok good solution!
Test #9:
score: 0
Accepted
time: 2ms
memory: 9840kb
input:
2 AB
output:
-1
result:
ok no solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 11860kb
input:
14 BAAAAAAAAAAAAA
output:
-1
result:
ok no solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 9728kb
input:
14 ABBABAABBABBAB
output:
7 8 2 9 2 6 2 6 2 5 2 2 2 1 2
result:
ok good solution!
Test #12:
score: 0
Accepted
time: 2ms
memory: 9788kb
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: 2ms
memory: 11780kb
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: 0ms
memory: 11752kb
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: 0ms
memory: 13836kb
input:
14 BBBABAAAAAAABA
output:
6 6 3 6 2 6 2 5 2 4 2 1 3
result:
ok good solution!
Test #16:
score: 0
Accepted
time: 0ms
memory: 13820kb
input:
15 AAAABABAAAAABAB
output:
7 8 3 8 2 7 2 6 2 5 2 1 2 1 2
result:
ok good solution!
Test #17:
score: 0
Accepted
time: 2ms
memory: 11820kb
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: 1ms
memory: 9784kb
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: 0ms
memory: 9852kb
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: 9788kb
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: 0ms
memory: 9772kb
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: 11832kb
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: 2ms
memory: 11896kb
input:
14 BABBBBBABAAAAA
output:
6 10 3 10 2 3 3 3 2 2 2 1 2
result:
ok good solution!
Test #24:
score: 0
Accepted
time: 1ms
memory: 9780kb
input:
15 BABAAAABABAAAAA
output:
7 11 3 11 2 4 2 4 2 3 2 2 2 1 2
result:
ok good solution!
Test #25:
score: 0
Accepted
time: 2ms
memory: 11788kb
input:
15 BAABABAABAABBAA
output:
7 7 2 8 2 6 2 6 2 5 3 2 2 1 2
result:
ok good solution!
Test #26:
score: 0
Accepted
time: 0ms
memory: 11812kb
input:
15 AABAABBAABAABAB
output:
7 8 2 9 2 6 2 6 2 4 3 3 2 1 2
result:
ok good solution!
Test #27:
score: 0
Accepted
time: 0ms
memory: 11832kb
input:
15 AABABBABAABBABB
output:
6 5 2 7 2 6 3 4 3 3 3 1 2
result:
ok good solution!
Test #28:
score: 0
Accepted
time: 0ms
memory: 9764kb
input:
15 BAABBABBAABABBA
output:
6 9 2 7 3 8 2 6 3 2 2 1 3
result:
ok good solution!
Test #29:
score: -3
Wrong Answer
time: 2ms
memory: 11808kb
input:
15 BBAABBABABABBAA
output:
7 5 2 3 3 7 2 6 3 3 3 1 3 1 2
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 1ms
memory: 9772kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
104 232 2 230 3 228 3 226 3 224 3 222 3 220 3 218 3 216 3 214 3 212 3 210 3 208 3 206 3 204 3 202 3 199 2 199 2 197 3 195 3 193 3 191 3 189 3 187 3 185 3 183 3 181 3 179 3 177 3 175 3 173 3 171 3 169 3 167 3 165 3 163 3 161 3 159 3 157 3 155 3 153 3 151 3 149 3 147 3 145 3 143 3 141 3 139 3 137 3 13...
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 7
Accepted
time: 0ms
memory: 9808kb
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: 11924kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 2001 2 2001 2 2000 2 1999 2 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 1...
result:
ok good solution!
Test #104:
score: 0
Accepted
time: 2ms
memory: 9884kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 4500 2 4497 2 4497 2 4496 2 4495 2 4494 2 4493 2 4492 2 4491 2 4490 2 4489 2 4488 2 4487 2 4486 2 4485 2 4484 2 4483 2 4482 2 4481 2 4480 2 4479 2 4478 2 4477 2 4476 2 4475 2 4474 2 4473 2 4472 2 4471 2 4470 2 4469 2 4468 2 4467 2 4466 2 4465 2 4464 2 4463 2 4462 2 4461 2 4460 2 4459 2 4458 2 4...
result:
ok good solution!
Test #105:
score: -7
Wrong Answer
time: 0ms
memory: 12000kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2999 1201 2 4196 2 4195 2 4195 2 4194 2 4193 2 4192 2 4191 2 4190 2 4189 2 4188 2 4187 2 4186 2 4185 2 4184 2 4183 2 4182 2 4181 2 4180 2 4179 2 4178 2 4177 2 4176 2 4175 2 4174 2 4173 2 4172 2 4171 2 4170 2 4169 2 4168 2 4167 2 4166 2 4165 2 4164 2 4163 2 4162 2 4161 2 4160 2 4159 2 4158 2 4157 2 4...
result:
wrong answer invalid operation on step #1803: AAB
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 9
Accepted
time: 42ms
memory: 24888kb
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: 38ms
memory: 25584kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333334 2 333334 2 333334 2 333333 2 333332 2 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 33330...
result:
ok good solution!
Test #155:
score: 0
Accepted
time: 37ms
memory: 25616kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499998 749999 2 749997 3 749996 2 749995 2 749994 2 749993 2 749992 2 749991 2 749990 2 749989 2 749988 2 749987 2 749986 2 749985 2 749984 2 749983 2 749982 2 749981 2 749980 2 749979 2 749978 2 749977 2 749976 2 749975 2 749974 2 749973 2 749972 2 749971 2 749970 2 749969 2 749968 2 749967 2 74996...
result:
ok good solution!
Test #156:
score: -9
Wrong Answer
time: 41ms
memory: 24892kb
input:
999998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 200001 2 699996 3 699995 3 699994 2 699993 2 699992 2 699991 2 699990 2 699989 2 699988 2 699987 2 699986 2 699985 2 699984 2 699983 2 699982 2 699981 2 699980 2 699979 2 699978 2 699977 2 699976 2 699975 2 699974 2 699973 2 699972 2 699971 2 699970 2 699969 2 699968 2 699967 2 699966 2 69996...
result:
wrong answer invalid operation on step #300002: AAB