QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#637405 | #4273. Good Game | chenxinyang2006 | 0 | 40ms | 37376kb | C++20 | 4.1kb | 2024-10-13 12:39:09 | 2024-10-13 12:39:10 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,m,k;
char s[1000005];
int a[1000005],b[1000005],c[1000005];
vector <pii> answer;
int top;
int stk[1000005];
void psh(int v){
// printf("psh %d\n",v);
stk[++top] = v;
}
int pick(){
assert(top);
return stk[top--];
}
void clr(int l,int r){
// printf("clr [%d,%d]\n",l,r);
assert(r > l);
if(l % 2 == r % 2){
answer.eb(l,3);
r -= 3;
}
while(l <= r){
answer.eb(l,2);
r -= 2;
}
}
struct info{
int _l[2],_r[2];
info(){
_l[0] = _l[1] = inf;
_r[0] = _r[1] = 0;
}
}dp[1000005];
void fix(info &I,int l,int r){
if(l > r) return;
assert(l % 2 == r % 2);
chkmin(I._l[l % 2],l);
chkmax(I._r[r % 2],r);
}
int sz;
int d[1000005];
void get(info &I,int up){
rep(i,I._l[0],min(up,I._r[0])) if(i % 2 == 0) d[++sz] = i;
rep(i,I._l[1],min(up,I._r[1])) if(i % 2) d[++sz] = i;
}
int chk(info &I,int p){
return I._l[p % 2] <= p && p <= I._r[p % 2];
}
int valid(int p,int l,int r){
return (p % 2 == l % 2 && l <= p && p <= r);
}
void dbg(info &I){
printf("even range [%d,%d] odd range [%d,%d]\n",I._l[0],I._r[0],I._l[1],I._r[1]);
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
scanf("%s",s + 1);
for(int l = 1,r;l <= n;l = r + 1){
r = l;
while(r < n && s[r] == s[r + 1]) r++;
a[++m] = r - l + 1;
}
k = 0;
rep(i,1,m){
if(a[i] == 1) b[k]++;
else c[++k] = a[i];
}
if(!k){
printf("-1\n");
return 0;
}
fix(dp[0],b[0],b[0]);
rep(i,1,k - 1){
get(dp[i - 1],b[i]);
while(sz){
fix(dp[i],b[i] - d[sz],b[i] - d[sz]);
fix(dp[i],abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1));
sz--;
}
rep(p,0,1){
int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
while(tl % 2 != p) tl++;
if(tl > tr) continue;
fix(dp[i],tl - (b[i] + 1),tr + (b[i] + 1));
}
dbg(dp[i]);
}
/* rep(i,1,m) printf("%d ",a[i]);
printf("\n");
rep(i,0,k) printf("%d ",b[i]);
printf("\n");
rep(i,1,k) printf("%d ",c[i]);
printf("\n");*/
if(!chk(dp[k - 1],b[k])){
printf("-1\n");
return 0;
}
rep(i,1,b[k]) psh(1);
int x = b[k],y,bb,sum = n - b[k];
per(i,k - 1,0){
y = x;x = bb = -1;
if(i){
get(dp[i - 1],b[i]);
while(sz){
if(b[i] - d[sz] == y) x = d[sz];
if(valid(y,abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1))) x = d[sz];
sz--;
}
// printf("x=%d\n",x);
rep(p,0,1){
int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
while(tl % 2 != p) tl++;
if(tl > tr || p + (b[i] + 1) % 2 != y % 2) continue;
chkmax(tl,y - (b[i] + 1));
chkmin(tr,y + (b[i] + 1));
if(tl <= tr) x = tl;
}
assert(x != -1);
bb = (b[i] + 1 - x + y) / 2;
}else{
x = 0;
bb = b[i];
}
// printf("i=%d bi=%d y=%d chose x=%d bb=%d sum=%d\n",i,b[i],y,x,bb,sum);
assert(x != -1);
assert(bb <= b[i] + 1);
sum -= c[i + 1];
psh(c[i + 1]);
rep(kk,1,bb){
clr(sum + 1,sum + pick());
if(kk != b[i] + 1){
stk[top]++;
sum--;
}else{
sum -= c[i];
c[i] += pick();
sum += c[i];
}
}
rep(kk,1,b[i] - bb){
psh(1);
sum--;
}
}
while(top) clr(1,stk[top--]);
printf("%d\n",SZ(answer));
for(pii I:answer) printf("%d %d\n",I.first,I.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
9 ABAABBBAA
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 0ms
memory: 30580kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
even range [32,34] odd range [1061109567,0] even range [1061109567,0] odd range [31,35] even range [30,36] odd range [1061109567,0] even range [1061109567,0] odd range [29,37] even range [28,38] odd range [1061109567,0] even range [1061109567,0] odd range [27,39] even range [26,40] odd range [106110...
result:
wrong output format Expected integer, but "even" found
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 0ms
memory: 26508kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
even range [0,0] odd range [1,3991] 2998 3995 3 3995 2 3995 2 3995 2 3994 2 3993 2 3992 2 3991 2 3990 2 3989 2 3988 2 3987 2 3986 2 3985 2 3984 2 3983 2 3982 2 3981 2 3980 2 3979 2 3978 2 3977 2 3976 2 3975 2 3974 2 3973 2 3972 2 3971 2 3970 2 3969 2 3968 2 3967 2 3966 2 3965 2 3964 2 3963 2 3962 2 ...
result:
wrong output format Expected integer, but "even" found
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 0
Wrong Answer
time: 40ms
memory: 37376kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
even range [0,0] odd range [1,666655] 499998 666661 2 666661 2 666661 2 666661 2 666661 2 666660 2 666659 2 666658 2 666657 2 666656 2 666655 2 666654 2 666653 2 666652 2 666651 2 666650 2 666649 2 666648 2 666647 2 666646 2 666645 2 666644 2 666643 2 666642 2 666641 2 666640 2 666639 2 666638 2 666...
result:
wrong output format Expected integer, but "even" found