QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211386#4273. Good Gamelmeowdn0 41ms31804kbC++143.4kb2023-10-12 15:43:052023-10-12 15:43:06

Judging History

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

  • [2023-10-12 15:43:06]
  • 评测
  • 测评结果:0
  • 用时:41ms
  • 内存:31804kb
  • [2023-10-12 15:43:05]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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]