QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211386 | #4273. Good Game | lmeowdn | 0 | 41ms | 31804kb | C++14 | 3.4kb | 2023-10-12 15:43:05 | 2023-10-12 15:43:06 |
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,x+1);
} else {
tans.eb(r-2,r);
for(int x=r-4;x>=l;x-=2) tans.eb(x,x+1);
}
}
printf("%d\n",(int)tans.size());
for(auto [l,r]:tans) printf("%d %d\n",l,r);
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7784kb
input:
9 ABAABBBAA
output:
4 3 4 4 5 2 3 1 3
result:
wrong answer Integer 4 violates the range [2, 3]
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 2ms
memory: 11804kb
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
35 34 35 33 35 32 34 31 33 30 32 29 31 28 30 29 30 27 28 26 28 25 27 24 26 23 25 22 24 21 23 20 22 19 21 18 20 17 19 16 18 15 17 14 16 13 15 12 14 11 13 10 12 9 11 8 10 7 9 6 8 5 7 4 6 3 5 2 4 1 3
result:
wrong answer wrong solution (expected NO SOLUTION)
Subtask #3:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 1ms
memory: 5836kb
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
2998 1998 1999 1996 1997 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 ...
result:
wrong answer Integer 1999 violates the range [2, 3]
Subtask #4:
score: 0
Wrong Answer
Test #153:
score: 0
Wrong Answer
time: 41ms
memory: 31804kb
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
499998 333332 333333 333330 333331 333328 333329 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...
result:
wrong answer Integer 333333 violates the range [2, 3]