QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#845980#9925. LR StringeastcloudWA 39ms5908kbC++233.2kb2025-01-06 20:46:232025-01-06 20:46:24

Judging History

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

  • [2025-01-06 20:46:24]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:5908kb
  • [2025-01-06 20:46:23]
  • 提交

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Fol(i,k,j) for(int i=(k);i>=(j);i--)

using namespace std;

#define N 500005

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

void debug(auto &&...x){
    ((cerr<<x<<' '),...);
    cerr<<'\n';
}

char s[N];
set<int> S;
int b[N],n;

struct seg{
    int v[N<<2];
    #define ls (x<<1)
    #define rs ((x<<1)|1)
    #define mid ((l+r)>>1)
    void build(int x,int l=1,int r=n){
        if(l==r)return v[x]=b[l],void();build(ls,l,mid);build(rs,mid+1,r);v[x]=max(v[ls],v[rs]);
    }
    int find(int x,int L,int R,int val,int l=1,int r=n){
        if(v[x]<val)return -1;
        if(l>=L && r<=R){
            if(l==r)return l;
            if(v[ls]>=val)return find(ls,L,R,val,l,mid);
            return find(rs,L,R,val,mid+1,r);
        }
        int res=-1;
        if(L<=mid)res=find(ls,L,R,val,l,mid);
        if(res==-1 && R>mid)res=find(rs,L,R,val,mid+1,r);return res;
    }
}T;

char t[N];

void solve(){
    scanf("%s",s+1);n=strlen(s+1);S.clear();
    int q=read();  
    For(i,1,n){
        if(s[i]=='L'){
            S.insert(i);
            int pos=i,len=0;
            while(pos+1<=n && s[pos+1]=='R')pos++,len++;
            b[i]=len;
        }
    }
    T.build(1);
    For(i,1,q){
        scanf("%s",t+1);int m=strlen(t+1),R=n,L=1,flag=1;
        if(m>n){printf("NO\n");continue;}
        while(m && t[m]=='L'){
            if(s[R]=='L')R--,m--;
            else {flag=0;break;}
        }
        if(!flag){printf("NO\n");continue;}
        if(!m){printf("YES\n");continue;}
        int lef=1;
        while(lef<=m && t[lef]=='R'){
            if(s[L]!='R'){flag=0;break;}
            L++;lef++;
        }
        if(!flag){printf("NO\n");continue;}
        while(lef<=m){
            if((lef<m && t[lef]=='L' && t[lef+1]=='L') || (lef==m && t[lef]=='L')){
                auto it=S.lower_bound(L);
                if(it==S.end() || (*it)>R){flag=0;break;}
                L=(*it)+1;lef++;
            }
            else{
                int len=1;lef++;
                while(lef+1<=m && t[lef+1]=='R')lef++,len++;lef++;
                if(L+len>R){flag=0;break;}
                int pos=T.find(1,L,R,len);
                if(pos==-1){flag=0;break;}
                if(pos+len>R){flag=0;break;}
                L=pos+len+1;
            }
        }
        if(!flag){printf("NO\n");continue;}
        printf("YES\n");
    }
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif
 
    int T=read();while(T--)solve();

}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5908kb

input:

2
RRLLRRLL
4
LLLLL
LLR
LRLR
R
RLLLLLL
3
LLLLL
RL
RRL

output:

NO
YES
NO
YES
YES
YES
NO

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 39ms
memory: 5868kb

input:

100000
RRLLR
4
R
R
R
R
LRLLL
6
R
L
L
L
L
R
RLLRR
1
L
LRLLL
3
R
L
L
RLRRL
2
LRRRR
RRRL
LRLRR
2
L
R
RRLRL
4
RLRLR
RLLL
LR
RLL
RLRLL
8
R
R
R
L
L
L
R
L
RLLRR
7
R
LL
RL
R
L
L
L
LLRLR
2
L
R
RRRRL
1
RLLLR
RRLLL
2
L
L
RLLRL
1
RLLRL
LRLLL
5
RLRLL
RLLLR
RRRRL
LLRRR
RLLRR
LRLLL
3
RRLL
R
RL
LLRRL
3
L
R
LLLRR
RR...

output:

YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
N...

result:

wrong answer 16th lines differ - expected: 'YES', found: 'NO'