QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73743#4273. Good Game123456780 55ms42536kbC++142.2kb2023-01-27 21:11:032023-01-27 21:11:06

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:11:06]
  • 评测
  • 测评结果:0
  • 用时:55ms
  • 内存:42536kb
  • [2023-01-27 21:11:03]
  • 提交

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
*/

詳細信息

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