QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73109#4273. Good GameFISHER_0 69ms25124kbC++142.1kb2023-01-22 11:16:452023-01-22 11:16:47

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:16:47]
  • 评测
  • 测评结果:0
  • 用时:69ms
  • 内存:25124kb
  • [2023-01-22 11:16:45]
  • 提交

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

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

9
ABAABBBAA

output:

3
3 2
2 4
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: 3824kb

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2994
1996 4
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
1955 2
1...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 0
Wrong Answer
time: 69ms
memory: 25124kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499992
333328 6
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
333298 2
333297 2
33329...

result:

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