QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211387#4273. Good Gamelmeowdn0 58ms51092kbC++143.4kb2023-10-12 15:43:542023-10-12 15:43:54

Judging History

你现在查看的是最新测评结果

  • [2023-10-12 15:43:54]
  • 评测
  • 测评结果:0
  • 用时:58ms
  • 内存:51092kb
  • [2023-10-12 15:43:54]
  • 提交

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;
}

详细

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