QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73109 | #4273. Good Game | FISHER_ | 0 | 69ms | 25124kb | C++14 | 2.1kb | 2023-01-22 11:16:45 | 2023-01-22 11:16:47 |
Judging History
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]