QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73110#4273. Good GameFISHER_0 63ms33840kbC++142.2kb2023-01-22 11:19:412023-01-22 11:19:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-22 11:19:43]
  • 评测
  • 测评结果:0
  • 用时:63ms
  • 内存:33840kb
  • [2023-01-22 11:19:41]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int maxn = 1000000;
char str[maxn + 5];
vector<pair<int, int>> op;
#define mid (s.size() >> 1)
void print0(int st, int c) {
	if (c & 1) op.emplace_back(st, 3), c -= 3;
	while (c) op.emplace_back(st, 2), c -= 2;
}
void print1(const vector<pair<int, int>>& s) {
	int sum = 0;
	for (int i = 0; i < mid; i++) sum += s[i].se;
	print0(sum + 1, s[mid].se);
	for (int i = 1; i <= mid; i++) {
		sum -= s[mid - i].se;
		print0(sum + 1, s[mid - i].se + s[mid + i].se);
	}
}
void print2(const vector<pair<int, int>>& s) {
	int l, r;
	for (l = mid; !s[l].fi; l--) ;
	for (r = mid; !s[r].fi; r++) ;
	int sum = 0;
	for (int i = 0; i < l; i++) sum += s[i].se;
	print0(sum + 1, s[l].se);
	for (int i = 1; i < r - mid; i++) {
		sum -= s[l - i].se;
		print0(sum + 1, s[l - i].se + s[l + i].se);
	}
	vector<pair<int, int>> lft(s.begin(), s.begin() + l - r + mid);
	lft.emplace_back(1, s[l - r + mid].se + s[l + r - mid].se);
	lft.insert(lft.end(), s.begin() + l + r - mid + 1, s.end());
	print1(lft);
}
bool ok[maxn + 5];
int main() {
	int n;
	scanf("%d%s", &n, str + 1);
	vector<pair<int, int>> s;
	for (int l = 1, r; l <= n; l = r + 1) {
		for (r = l; r < n && str[r + 1] == str[l]; r++) ;
		s.emplace_back(r > l, r - l + 1);
	}
	if (s.size() % 2 == 1) {
		if (s[mid].fi) print1(s);
		else {
			int mx = 0, nw = 0;
			for (const auto& x : s) mx = max(mx, nw = x.fi ? nw + 1 : 0);
			if (mx < mid) print2(s);
			else return printf("-1"), 0;
		}
	} else {
		int mx = 0, nw = 0;
		for (int i = s.size() - 1; ~i; i--) {
			mx = max(mx, nw = s[i].fi ? nw + 1 : 0);
			if (i & 1) ok[i] = mx < (s.size() - i) / 2 || s[(s.size() + i) / 2].fi;
		}
		mx = nw = 0;
		for (int i = 0; i < s.size(); i++) {
			mx = max(mx, nw = s[i].fi ? nw + 1 : 0);
			if (i & 1 ^ 1 && ok[i + 1] && (mx < i / 2 || s[i / 2].fi)) {
				vector<pair<int, int>> s1(s.begin(), s.begin() + i + 1), s2(s.begin() + i + 1, s.end());
				s[i / 2].fi ? print1(s1) : print2(s1);
				s[(s.size() + i) / 2].fi ? print1(s2) : print2(s2);
				goto ed;
			} 
		}
		return printf("-1"), 0;
	}
	ed: printf("%zu\n", op.size());
	for (const auto& p : op) printf("%d %d\n", p.fi, p.se);
} 

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 3
Accepted
time: 2ms
memory: 3588kb

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: 3624kb

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: 3596kb

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: 3644kb

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: 0ms
memory: 3584kb

input:

1
B

output:

-1

result:

ok no solution

Test #6:

score: 0
Accepted
time: 2ms
memory: 3592kb

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

7
AAAABBB

output:

3
1 2
1 2
1 3

result:

ok good solution!

Test #8:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

11
BBBBBBAAAAA

output:

5
1 2
1 2
1 2
1 3
1 2

result:

ok good solution!

Test #9:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

2
AB

output:

-1

result:

ok no solution

Test #10:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

14
BAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #11:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

14
ABBABAABBABBAB

output:

7
2 2
1 2
4 2
5 2
2 2
2 2
1 2

result:

ok good solution!

Test #12:

score: 0
Accepted
time: 2ms
memory: 3656kb

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: 0ms
memory: 3580kb

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: 2ms
memory: 3616kb

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: 2ms
memory: 3600kb

input:

14
BBBABAAAAAAABA

output:

6
1 3
3 3
3 2
3 2
2 2
1 2

result:

ok good solution!

Test #16:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

15
AAAABABAAAAABAB

output:

7
1 2
1 2
4 3
4 2
3 2
2 2
1 2

result:

ok good solution!

Test #17:

score: 0
Accepted
time: 0ms
memory: 3624kb

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: 2ms
memory: 3704kb

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: 1ms
memory: 3672kb

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: 3660kb

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: 2ms
memory: 3656kb

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: 3536kb

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: 0ms
memory: 3624kb

input:

14
BABBBBBABAAAAA

output:

6
3 3
3 2
2 2
1 2
1 3
1 2

result:

ok good solution!

Test #24:

score: -3
Memory Limit Exceeded

input:

15
BABAAAABABAAAAA

output:


result:


Subtask #2:

score: 0
Memory Limit Exceeded

Test #51:

score: 0
Memory Limit Exceeded

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:


result:


Subtask #3:

score: 0
Memory Limit Exceeded

Test #102:

score: 7
Accepted
time: 3ms
memory: 3776kb

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: 3824kb

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: -7
Memory Limit Exceeded

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:


result:


Subtask #4:

score: 0
Memory Limit Exceeded

Test #153:

score: 9
Accepted
time: 61ms
memory: 24936kb

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: 63ms
memory: 33840kb

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: -9
Memory Limit Exceeded

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:


result: