QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73108 | #4273. Good Game | FISHER_ | 0 | 78ms | 25096kb | C++14 | 2.2kb | 2023-01-22 11:13:57 | 2023-01-22 11:13:58 |
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 + 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);
}
Details
Tip: Click on the bar to expand more detailed information
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]