QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73744#4273. Good Game123456780 85ms57984kbC++142.9kb2023-01-27 21:21:322023-01-27 21:21:33

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-27 21:21:33]
  • 评测
  • 测评结果:0
  • 用时:85ms
  • 内存:57984kb
  • [2023-01-27 21:21:32]
  • 提交

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);
}
int tag[1000005];
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 {
		int mx = 0, s = 0;
		for(int i = (int)a.size() - 1; i >= 0; i--) {
			if(a[i] < 2) s++;
			else s = 0;
			mx = max(mx, s);
			if(i & 1) tag[i] = (mx < ((int)a.size() - i)  / 2 || a[((int)a.size()+i)/2] >= 2);
		}
		mx = 0, s = 0;
		for(int i = 0; i < (int)a.size(); i++) {
			if(a[i] < 2) s++;
			else s = 0;
			mx = max(mx, s);
			if(!(i & 1) && tag[i+1] && (mx < i / 2 || a[i/2] >= 2)) {
				vector<int> s1(a.begin(), a.begin() + i + 1), s2(a.begin() + i + 1, a.end());
				if(s1[(int)s1.size()/2] >= 2) print1(s1);
				else print2(s1);
				if(s2[(int)s2.size()/2] >= 2) print1(s2);
				else print2(s2);
				break;
			}
			if(i == (int)a.size() - 1) return printf("-1\n") & 1;
		}
	}
	write((int)Ans.size()), putchar('\n');
	for(auto x : Ans) write(x.first), putchar(' '), write(x.second), putchar('\n');
	return 0;
}
/*
10
BBABBAABAB
*/

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 3
Accepted
time: 0ms
memory: 3432kb

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

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

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

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

input:

1
B

output:

-1

result:

ok no solution

Test #6:

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

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

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

input:

7
AAAABBB

output:

3
1 2
1 2
1 3

result:

ok good solution!

Test #8:

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

input:

11
BBBBBBAAAAA

output:

5
1 2
1 2
1 2
1 3
1 2

result:

ok good solution!

Test #9:

score: -3
Runtime Error

input:

2
AB

output:

-1

result:


Subtask #2:

score: 0
Runtime Error

Test #51:

score: 0
Runtime Error

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:


Subtask #3:

score: 0
Runtime Error

Test #102:

score: 7
Accepted
time: 2ms
memory: 3548kb

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

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: 0
Accepted
time: 2ms
memory: 3648kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
1499 3
1498 3
1497 2
1496 2
1495 2
1494 2
1493 2
1492 2
1491 2
1490 2
1489 2
1488 2
1487 2
1486 2
1485 2
1484 2
1483 2
1482 2
1481 2
1480 2
1479 2
1478 2
1477 2
1476 2
1475 2
1474 2
1473 2
1472 2
1471 2
1470 2
1469 2
1468 2
1467 2
1466 2
1465 2
1464 2
1463 2
1462 2
1461 2
1460 2
1459 2
1458 2
1...

result:

ok good solution!

Test #105:

score: 0
Accepted
time: 3ms
memory: 3668kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
1201 2
1198 2
1198 2
1197 2
1196 2
1195 2
1194 2
1193 2
1192 2
1191 2
1190 2
1189 2
1188 2
1187 2
1186 2
1185 2
1184 2
1183 2
1182 2
1181 2
1180 2
1179 2
1178 2
1177 2
1176 2
1175 2
1174 2
1173 2
1172 2
1171 2
1170 2
1169 2
1168 2
1167 2
1166 2
1165 2
1164 2
1163 2
1162 2
1161 2
1160 2
1159 2
1...

result:

ok good solution!

Test #106:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
1199 2
1198 2
1197 2
1196 2
1195 2
1194 2
1193 2
1192 2
1191 2
1190 2
1189 2
1188 2
1187 2
1186 2
1185 2
1184 2
1183 2
1182 2
1181 2
1180 2
1179 2
1178 2
1177 2
1176 2
1175 2
1174 2
1173 2
1172 2
1171 2
1170 2
1169 2
1168 2
1167 2
1166 2
1165 2
1164 2
1163 2
1162 2
1161 2
1160 2
1159 2
1158 2
1...

result:

ok good solution!

Test #107:

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

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
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
1960 2
1959 2
1958 2
1957 2
1...

result:

ok good solution!

Test #108:

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

input:

5997
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

2998
1 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2...

result:

ok good solution!

Test #109:

score: -7
Runtime Error

input:

6000
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

-1

result:


Subtask #4:

score: 0
Runtime Error

Test #153:

score: 9
Accepted
time: 63ms
memory: 42420kb

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: 78ms
memory: 57984kb

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: 0
Accepted
time: 85ms
memory: 43880kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
249999 2
249998 2
249998 2
249997 2
249996 2
249995 2
249994 2
249993 2
249992 2
249991 2
249990 2
249989 2
249988 2
249987 2
249986 2
249985 2
249984 2
249983 2
249982 2
249981 2
249980 2
249979 2
249978 2
249977 2
249976 2
249975 2
249974 2
249973 2
249972 2
249971 2
249970 2
249969 2
24996...

result:

ok good solution!

Test #156:

score: 0
Accepted
time: 58ms
memory: 46640kb

input:

999998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
200001 2
199998 2
199998 2
199997 2
199996 2
199995 2
199994 2
199993 2
199992 2
199991 2
199990 2
199989 2
199988 2
199987 2
199986 2
199985 2
199984 2
199983 2
199982 2
199981 2
199980 2
199979 2
199978 2
199977 2
199976 2
199975 2
199974 2
199973 2
199972 2
199971 2
199970 2
199969 2
19996...

result:

ok good solution!

Test #157:

score: 0
Accepted
time: 65ms
memory: 46664kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499999
199999 2
199999 2
199998 2
199997 2
199996 2
199995 2
199994 2
199993 2
199992 2
199991 2
199990 2
199989 2
199988 2
199987 2
199986 2
199985 2
199984 2
199983 2
199982 2
199981 2
199980 2
199979 2
199978 2
199977 2
199976 2
199975 2
199974 2
199973 2
199972 2
199971 2
199970 2
199969 2
19996...

result:

ok good solution!

Test #158:

score: 0
Accepted
time: 66ms
memory: 45120kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
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
333304 2
333303 2
333302 2
333301 2
333300 2
33329...

result:

ok good solution!

Test #159:

score: 0
Accepted
time: 17ms
memory: 12340kb

input:

999999
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

499999
1 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:

ok good solution!

Test #160:

score: -9
Runtime Error

input:

999998
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result: