QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211387 | #4273. Good Game | lmeowdn | 0 | 58ms | 51092kb | C++14 | 3.4kb | 2023-10-12 15:43:54 | 2023-10-12 15:43:54 |
Judging History
answer
//vanitas vanitatum et omnia
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1e6+5;
int n,m,tt,del[N];
struct node {int x,l,r;} a[N];
char s[N];
vp ans,tans;
int Del(int c,int r,int z=N,int d=0) {
int x=c-1,y=c+1,res=0;
rep(i,1,r) {
while(del[x]) x--;
while(del[y]) y++;
pii p(a[c].l-(x+1>z)*d,a[c].r-(x+1>z)*d);
res+=p.se-p.fi+1, ans.eb(p);
//cout<<"D "<<c<<' '<<x<<' '<<y<<endl;
a[c].l=a[x].l;
a[c].r=a[x].r+a[y].r-a[y].l+1;
del[x]=del[y]=1, x--, y++;
} return res;
}
bool Getodd(int L,int R) {
int n=R-L+1;
int c=L-1+(n+1)/2,l=c,r=c,p=(n+1)/2;
if(a[c].x==1) {
Del(c,p-1);
ans.eb(a[c].l,a[c].r);
return 1;
}
while(l>=L&&!a[l].x) --l;
while(r<=R&&!a[r].x) ++r;
if(l<L||r>R) return 0;
if(r-l>=p) return 0;
if(r-c<=c-l) {
int d=Del(l,r-c);
//rep(i,1,n) if(!del[i]) cout<<i<<" "<<a[i].l<<" "<<a[i].r<<endl;
//cout<<d<<endl;
Del(r,p-1-(r-c),l,d);
ans.eb(a[r].l,a[r].r);
} else {
Del(r,p-c); Del(l,p-1-(p-c));
ans.eb(a[l].l,a[l].r);
}
return 1;
}
bool Geteven() {
static int f[N],pre[N],suf[N],lst[N],nxt[N];
rep(i,1,n) lst[i]=(a[i].x==1?i:lst[i-1]);
per(i,n,1) nxt[i]=(a[i].x==1?i:nxt[i+1]);
rep(i,1,n) if(!a[i].x) f[i]=nxt[i]-lst[i]-1;
rep(i,1,n) if(i&1) pre[i]=min(i,f[(i+1)/2]);
rep(i,1,n) pre[i]=(pre[i]==0||pre[i]*2+1<i);
per(i,n,1) if((n-i+1)&1) suf[i]=min(n-i+1,f[(i+n)/2]);
per(i,n,1) suf[i]=(suf[i]==0||suf[i]*2+1<n-i+1);
rep(i,1,n) if((i&1)&&pre[i]&&suf[i+1]) {
//cout<<i<<endl;
Getodd(i+1,n), Getodd(1,i);
return 1;
} return 0;
}
signed main() {
scanf("%d%s",&n,s+1);
rep(i,1,n) {
int l=i, r=i;
while(r<=n&&s[r]==s[l]) r++; r--;
//cout<<l<<" "<<r<<endl;
a[++m]=(node){l!=r,l,r}; i=r;
}
n=m;
//rep(i,1,n) cout<<a[i].x<<" "; puts("");
if(n&1) tt=Getodd(1,n);
else tt=Geteven();
if(!tt) puts("-1");
for(auto [l,r]:ans) {
if((r-l)&1) {
for(int x=r-1;x>=l;x-=2) tans.eb(x,2);
} else {
tans.eb(r-2,3);
for(int x=r-4;x>=l;x-=2) tans.eb(x,2);
}
}
printf("%d\n",(int)tans.size());
for(auto [l,r]:tans) printf("%d %d\n",l,r);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 1ms
memory: 5724kb
input:
9 ABAABBBAA
output:
4 3 2 4 2 2 2 1 3
result:
ok good solution!
Test #2:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
13 ABABBABABBABA
output:
6 4 2 3 2 5 2 4 2 2 3 1 2
result:
ok good solution!
Test #3:
score: 0
Accepted
time: 1ms
memory: 11856kb
input:
15 AABABAABABAABAB
output:
7 6 2 5 2 7 2 6 2 4 3 3 2 1 2
result:
ok good solution!
Test #4:
score: 0
Accepted
time: 0ms
memory: 11928kb
input:
15 ABAABBBABAABBAB
output:
7 12 2 10 3 9 2 3 2 4 2 2 2 1 2
result:
ok good solution!
Test #5:
score: -3
Wrong Answer
time: 0ms
memory: 7744kb
input:
1 B
output:
-1 0
result:
wrong output format Extra information in the output file
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 1ms
memory: 9848kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
35 34 2 33 3 32 3 31 3 30 3 29 3 28 3 29 2 27 2 26 3 25 3 24 3 23 3 22 3 21 3 20 3 19 3 18 3 17 3 16 3 15 3 14 3 13 3 12 3 11 3 10 3 9 3 8 3 7 3 6 3 5 3 4 3 3 3 2 3 1 3
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 7
Accepted
time: 2ms
memory: 7888kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1998 2 1996 2 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 1...
result:
ok good solution!
Test #103:
score: 0
Accepted
time: 2ms
memory: 12092kb
input:
5999 BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 2003 2 2001 2 2000 2 1999 2 1998 2 1997 2 1996 2 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 1...
result:
ok good solution!
Test #104:
score: 0
Accepted
time: 2ms
memory: 12044kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 4500 2 4499 2 4497 2 4496 2 4495 2 4494 2 4493 2 4492 2 4491 2 4490 2 4489 2 4488 2 4487 2 4486 2 4485 2 4484 2 4483 2 4482 2 4481 2 4480 2 4479 2 4478 2 4477 2 4476 2 4475 2 4474 2 4473 2 4472 2 4471 2 4470 2 4469 2 4468 2 4467 2 4466 2 4465 2 4464 2 4463 2 4462 2 4461 2 4460 2 4459 2 4458 2 4...
result:
ok good solution!
Test #105:
score: 0
Accepted
time: 2ms
memory: 10064kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2999 4198 2 4199 2 4197 2 4196 2 4195 2 4194 2 4193 2 4192 2 4191 2 4190 2 4189 2 4188 2 4187 2 4186 2 4185 2 4184 2 4183 2 4182 2 4181 2 4180 2 4179 2 4178 2 4177 2 4176 2 4175 2 4174 2 4173 2 4172 2 4171 2 4170 2 4169 2 4168 2 4167 2 4166 2 4165 2 4164 2 4163 2 4162 2 4161 2 4160 2 4159 2 4158 2 4...
result:
ok good solution!
Test #106:
score: 0
Accepted
time: 2ms
memory: 10112kb
input:
5999 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2999 4197 3 4199 2 4197 2 4195 2 4194 2 4193 2 4192 2 4191 2 4190 2 4189 2 4188 2 4187 2 4186 2 4185 2 4184 2 4183 2 4182 2 4181 2 4180 2 4179 2 4178 2 4177 2 4176 2 4175 2 4174 2 4173 2 4172 2 4171 2 4170 2 4169 2 4168 2 4167 2 4166 2 4165 2 4164 2 4163 2 4162 2 4161 2 4160 2 4159 2 4158 2 4157 2 4...
result:
ok good solution!
Test #107:
score: 0
Accepted
time: 2ms
memory: 12020kb
input:
5998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
2998 4996 3 4996 3 4994 2 4993 2 4992 2 4991 2 4990 2 4989 2 4988 2 4987 2 4986 2 4985 2 4984 2 4983 2 4982 2 4981 2 4980 2 4979 2 4978 2 4977 2 4976 2 4975 2 4974 2 4973 2 4972 2 4971 2 4970 2 4969 2 4968 2 4967 2 4966 2 4965 2 4964 2 4963 2 4962 2 4961 2 4960 2 4959 2 4958 2 4957 2 4956 2 4955 2 4...
result:
ok good solution!
Test #108:
score: 0
Accepted
time: 0ms
memory: 5828kb
input:
5997 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
2998 5995 3 5993 2 5991 2 5989 2 5987 2 5985 2 5983 2 5981 2 5979 2 5977 2 5975 2 5973 2 5971 2 5969 2 5967 2 5965 2 5963 2 5961 2 5959 2 5957 2 5955 2 5953 2 5951 2 5949 2 5947 2 5945 2 5943 2 5941 2 5939 2 5937 2 5935 2 5933 2 5931 2 5929 2 5927 2 5925 2 5923 2 5921 2 5919 2 5917 2 5915 2 5913 2 5...
result:
ok good solution!
Test #109:
score: -7
Wrong Answer
time: 2ms
memory: 11932kb
input:
6000 ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
-1 0
result:
wrong output format Extra information in the output file
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 9
Accepted
time: 58ms
memory: 31772kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333332 2 333330 2 333328 2 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 33329...
result:
ok good solution!
Test #154:
score: 0
Accepted
time: 47ms
memory: 50204kb
input:
999998 BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333338 2 333336 2 333334 2 333333 2 333332 2 333331 2 333330 2 333329 2 333328 2 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 33330...
result:
ok good solution!
Test #155:
score: 0
Accepted
time: 38ms
memory: 50688kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499998 749999 2 749997 3 749996 2 749995 2 749994 2 749993 2 749992 2 749991 2 749990 2 749989 2 749988 2 749987 2 749986 2 749985 2 749984 2 749983 2 749982 2 749981 2 749980 2 749979 2 749978 2 749977 2 749976 2 749975 2 749974 2 749973 2 749972 2 749971 2 749970 2 749969 2 749968 2 749967 2 74996...
result:
ok good solution!
Test #156:
score: 0
Accepted
time: 38ms
memory: 51092kb
input:
999998 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 699998 3 699997 3 699996 2 699995 2 699994 2 699993 2 699992 2 699991 2 699990 2 699989 2 699988 2 699987 2 699986 2 699985 2 699984 2 699983 2 699982 2 699981 2 699980 2 699979 2 699978 2 699977 2 699976 2 699975 2 699974 2 699973 2 699972 2 699971 2 699970 2 699969 2 699968 2 699967 2 69996...
result:
ok good solution!
Test #157:
score: 0
Accepted
time: 42ms
memory: 50412kb
input:
999999 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499999 700000 2 699999 3 699997 2 699996 2 699995 2 699994 2 699993 2 699992 2 699991 2 699990 2 699989 2 699988 2 699987 2 699986 2 699985 2 699984 2 699983 2 699982 2 699981 2 699980 2 699979 2 699978 2 699977 2 699976 2 699975 2 699974 2 699973 2 699972 2 699971 2 699970 2 699969 2 699968 2 69996...
result:
ok good solution!
Test #158:
score: 0
Accepted
time: 46ms
memory: 49876kb
input:
999997 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
499998 833329 3 833329 2 833327 2 833326 2 833325 2 833324 2 833323 2 833322 2 833321 2 833320 2 833319 2 833318 2 833317 2 833316 2 833315 2 833314 2 833313 2 833312 2 833311 2 833310 2 833309 2 833308 2 833307 2 833306 2 833305 2 833304 2 833303 2 833302 2 833301 2 833300 2 833299 2 833298 2 83329...
result:
ok good solution!
Test #159:
score: 0
Accepted
time: 36ms
memory: 12300kb
input:
999999 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
499999 999997 3 999995 2 999993 2 999991 2 999989 2 999987 2 999985 2 999983 2 999981 2 999979 2 999977 2 999975 2 999973 2 999971 2 999969 2 999967 2 999965 2 999963 2 999961 2 999959 2 999957 2 999955 2 999953 2 999951 2 999949 2 999947 2 999945 2 999943 2 999941 2 999939 2 999937 2 999935 2 99993...
result:
ok good solution!
Test #160:
score: -9
Wrong Answer
time: 5ms
memory: 12832kb
input:
999998 BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1 0
result:
wrong output format Extra information in the output file