QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73108#4273. Good GameFISHER_0 78ms25096kbC++142.2kb2023-01-22 11:13:572023-01-22 11:13:58

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:13:58]
  • 评测
  • 测评结果:0
  • 用时:78ms
  • 内存:25096kb
  • [2023-01-22 11:13:57]
  • 提交

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 print1(const vector<pair<int, int>>& s) {
	int sum = 0;
	for (int i = 0; i < mid; i++) sum += s[i].se;
	op.emplace_back(sum + 1, sum + s[mid].se);
	for (int i = 1; i <= mid; i++) {
		sum -= s[mid - i].se;
		op.emplace_back(sum + 1, sum + 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;
	op.emplace_back(sum + 1, sum + s[l].se);
	for (int i = 1; i < r - mid; i++) {
		sum -= s[l - i].se;
		op.emplace_back(sum + 1, sum + 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);
} 

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3648kb

input:

9
ABAABBBAA

output:

3
3 4
2 5
1 3

result:

wrong answer Integer 4 violates the range [2, 3]

Subtask #2:

score: 0
Dangerous Syscalls

Test #51:

score: 0
Dangerous Syscalls

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:


result:


Subtask #3:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 2ms
memory: 3776kb

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2994
1996 1999
1995 1996
1994 1995
1993 1994
1992 1993
1991 1992
1990 1991
1989 1990
1988 1989
1987 1988
1986 1987
1985 1986
1984 1985
1983 1984
1982 1983
1981 1982
1980 1981
1979 1980
1978 1979
1977 1978
1976 1977
1975 1976
1974 1975
1973 1974
1972 1973
1971 1972
1970 1971
1969 1970
1968 1969
1967 ...

result:

wrong answer Integer 1999 violates the range [2, 3]

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 0
Wrong Answer
time: 78ms
memory: 25096kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499992
333328 333333
333327 333328
333326 333327
333325 333326
333324 333325
333323 333324
333322 333323
333321 333322
333320 333321
333319 333320
333318 333319
333317 333318
333316 333317
333315 333316
333314 333315
333313 333314
333312 333313
333311 333312
333310 333311
333309 333310
333308 333309...

result:

wrong answer Integer 333333 violates the range [2, 3]