QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334779#4273. Good GameMax_s_xaM0 42ms25616kbC++143.9kb2024-02-22 13:34:222024-02-22 13:34:23

Judging History

你现在查看的是最新测评结果

  • [2024-02-22 13:34:23]
  • 评测
  • 测评结果:0
  • 用时:42ms
  • 内存:25616kb
  • [2024-02-22 13:34:22]
  • 提交

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