QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72944#4273. Good GameSSL_TJH0 4ms9204kbC++142.8kb2023-01-20 21:30:112023-01-20 21:30:12

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-20 21:30:12]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:9204kb
  • [2023-01-20 21:30:11]
  • 提交

answer

#include<cstdio>
#include<vector>

using namespace std;

const int N = 1e6 + 100;
int n, m, ls[N], rs[N], a[N], Ls[N], Rs[N];
char s[N];
vector <pair<int, int> > ans;
bool shit;

void write() {
	if (shit) {printf("-1"); return ;}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
}

void clean(int l, int sz) {
	if (sz & 1) ans.push_back(make_pair(l, 3)), sz -= 3;
	while (sz) ans.push_back(make_pair(l, 2)), sz -= 2;
}

void lnk_clean(int x, int y) {
	clean(ls[x], rs[x] - ls[x] + 1 + ((x ^ y) ? rs[y] - ls[y] + 1 : 0));
}

void work() {
	if (shit) return ;
	int k = (m + 1) / 2;
	if (a[k] == 2) {
		int clsz = 0;
		for (int i = 1; i <= k; i++) {
			int l = k - i + 1, r = k + i - 1;
			clean(ls[l], rs[r] - ls[l] + 1 - clsz);
			clsz = rs[r] - ls[l] + 1;
		}
		return ;
	}
	int lc = -1, rc = -1;
	for (int i = k - 1; i >= 1; i--) if (a[i] == 2) {lc = i; break;}
	for (int i = k + 1; i <= m; i++) if (a[i] == 2) {rc = i; break;}
	if (lc == -1 || rc == -1) {shit = 1; return ;}
	int dis = min(k - lc + 1, rc - k + 1);
	if (k - lc > rc - k) {
		for (int i = 1; i <= dis; i++) lnk_clean(rc - i + 1, rc + i - 1);
		int tmp = rs[rc + dis - 1] - ls[rc - dis + 1] + 1;
		for (int i = rc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
		m -= dis * 2;
	}
	else {
		for (int i = 1; i <= dis; i++) lnk_clean(lc - i + 1, lc + i - 1);
		int tmp = rs[lc + dis - 1] - ls[lc - dis + 1] + 1;
		for (int i = lc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
		m -= dis * 2;
	}
	k = (m + 1) / 2;
	int clsz = 0;
	for (int i = 1; i <= k; i++) {
		int l = k - i + 1, r = k + i - 1;
		clean(ls[l], rs[r] - ls[l] + 1 - clsz);
		clsz = rs[r] - ls[l] + 1;
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	
	for (int L = 1, R; L <= n; L = R + 1) {
		R = L; while (R < n && s[R + 1] == s[R]) R++;
		m++; ls[m] = L; rs[m] = R; if (L != R) a[m] = 2; else a[m] = 1;
	}
	
	int num = 0;
	for (int i = 1; i <= m; i++) {
		if (a[i] == 2) Ls[i] = Ls[i - 1], num = 0;
			else {
				num++; Ls[i] = max(Ls[i - 1], num);
			}
	}
	num = 0;
	for (int i = m; i >= 1; i--) {
		if (a[i] == 2) Rs[i] = Rs[i + 1], num = 0;
			else {
				num++; Rs[i] = max(Rs[i + 1], num);
			}
	}
	
	if (m & 1) {work(); write(); return 0;}
	
	int bk = -1;
	for (int i = 1; i <= m; i += 2)
		if ((a[(i + 1) / 2] == 2 || Ls[i] < i / 2) && (a[(m + i + 1) / 2] == 2 || Rs[i + 1] < (m - i) / 2)) {
			bk = i; break;
		}
	if (bk == -1) shit = 1;
	int tmp = m, tmp_d = rs[bk];
	m = bk; work(); m = tmp;
	for (int i = bk + 1; i <= m; i++) ls[i - bk] = ls[i] - tmp_d, rs[i - bk] = rs[i] - tmp_d, a[i - bk] = a[i];
	m = m - bk; work(); m = tmp;
	write();
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 3
Accepted
time: 1ms
memory: 9128kb

input:

9
ABAABBBAA

output:

4
3 2
2 2
2 2
1 3

result:

ok good solution!

Test #2:

score: -3
Time Limit Exceeded

input:

13
ABABBABABBABA

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #51:

score: 6
Accepted
time: 4ms
memory: 9088kb

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #52:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #53:

score: -6
Time Limit Exceeded

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #102:

score: 0
Time Limit Exceeded

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #153:

score: 0
Time Limit Exceeded

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:


result: