QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106863#6400. Game: Celestewhatever#WA 96ms19872kbC++173.3kb2023-05-19 16:15:582023-05-19 16:18:20

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-19 16:18:20]
  • Judged
  • Verdict: WA
  • Time: 96ms
  • Memory: 19872kb
  • [2023-05-19 16:15:58]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(y<x)x=y;}

#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;

typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;

namespace orzjk{
  const int SZ=1e6;
  char buf[SZ],*p1=buf,*p2=buf;
  char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;
  }
  char fub[SZ],*p3=fub,*p4=fub+SZ;
  void pc(char c){
    p3==p4&&(fwrite(fub,1,SZ,stdout),p3=fub);
    *p3++=c;
  }
  void flush(){
    fwrite(fub,1,p3-fub,stdout),p3=fub;
  }
}
using orzjk::nc;
using orzjk::pc;

//#define nc getchar
//#define pc putchar

int read(){
  int x=0,f=1;char c=nc();
  while(c<48)c=='-'&&(f=-1),c=nc();
  while(c>47)x=x*10+(c^48),c=nc();
  return x*f;
}
template<class T>void write(T x){
  static char st[41];
  if(!x)return pc(48),void();
  char*p=st;
  if(x<0)x=-x,pc('-');
  for(;x;x/=10)*p++=x%10|48;
  do{
    pc(*--p);
  }while(p!=st);
}

//const int P=1e9+7;
const int P=998244353;
int qp(int a,int k){
  int res=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)res=1ll*res*a%P;return res;
}

const int B=19260817;

const int maxn=1e6+10;
int n,L,R,x[maxn],a[maxn];

int pw[maxn];

#define mid ((l+r)/2)

int tot,rt[maxn];
int ls[maxn],rs[maxn],val[maxn];
void ins(int&k,int rt,int l,int r,int x){
  k=++tot,ls[k]=ls[rt],rs[k]=rs[rt];
  if(l==r){
    val[k]=val[rt]+1;
  }else{
    x<=mid?ins(ls[k],ls[rt],l,mid,x):ins(rs[k],rs[rt],mid+1,r,x);
    val[k]=(1ll*val[ls[k]]*pw[r-mid]+val[rs[k]])%P;
  }
}
int leq(int a,int b,int l,int r){
  if(l==r){
    return val[a]<=val[b];
  }
  if(val[rs[a]]==val[rs[b]]){
    return leq(ls[a],ls[b],l,mid);
  }else{
    return leq(ls[a],ls[b],mid+1,r);
  }
}

vi out;
void dfs(int k,int l,int r){
  if(l==r){
    rep(i,1,val[k])out.pb(l);
  }else{
    dfs(rs[k],mid+1,r);
    dfs(ls[k],l,mid);
  }
}

#undef mid

void solve(){
  n=read(),L=read(),R=read();
  rep(i,1,n)x[i]=read();
  rep(i,1,n)a[i]=read();
  
  tot=0;
  ins(rt[1],0,1,n,a[1]);
  
  static bool can[maxn];
  can[1]=1;
  rep(i,2,n)can[i]=0;
  
  static int Q[maxn];
  int l=1,r=0;
  
  for(int i=2,cur=0;i<=n;i++){
    while(cur+1<i&&x[cur+1]+L<=x[i]){
      ++cur;
      if(!can[cur])continue;
      while(l<=r&&leq(rt[Q[r]],rt[cur],1,n))r--;
      Q[++r]=cur;
    }
    while(l<=r&&x[Q[l]]+R<x[i]){
      l++;
    }
    if(l<=r){
      can[i]=1;
      ins(rt[i],rt[Q[l]],1,n,a[i]);
    }
  }
  if(can[n]){
    out.clear();
    dfs(rt[n],1,n);
    write(out.size()),pc(10);
    for(int x:out)write(x),pc(32);
    pc(10);
  }else{
    pc('-');
    pc('1');
    pc(10);
  }
}

signed main(){
  pw[0]=1;
  rep(i,1,maxn-1)pw[i]=1ll*B*pw[i-1]%P;
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
  int T;cin>>T;while(T--)solve();
//  solve();
  orzjk::flush();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 19872kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

3
5 4 3 
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 96ms
memory: 19844kb

input:

10000
57 8 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...

output:

7
20 11 11 11 4 3 1 
-1
6
6 5 3 2 1 1 
-1
185
20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12...

result:

wrong answer 2nd lines differ - expected: '20 20 19 14 12 11 3', found: '20 11 11 11 4 3 1 '