QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106866#6400. Game: Celestewhatever#RE 201ms30204kbC++173.3kb2023-05-19 16:20:522023-05-19 16:20:54

Judging History

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

  • [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:20:54]
  • 评测
  • 测评结果:RE
  • 用时:201ms
  • 内存:30204kb
  • [2023-05-19 16:20:52]
  • 提交

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(rs[a],rs[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;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 17564kb

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: 0
Accepted
time: 116ms
memory: 19840kb

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 20 19 14 12 11 3 
-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 ...

result:

ok 16378 lines

Test #3:

score: 0
Accepted
time: 76ms
memory: 17664kb

input:

10000
86 230405 991217
3291 11742 17120 30018 47955 52215 96227 98031 100118 106944 117304 121905 124796 135037 164100 164654 169459 177527 206513 212554 228740 229590 261521 295062 300116 312030 326533 329513 349983 353580 355242 356731 363347 368753 389545 396163 399755 409927 426532 427781 441386...

output:

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

result:

ok 14975 lines

Test #4:

score: 0
Accepted
time: 93ms
memory: 19992kb

input:

10000
101 17 17
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

-1
15
10 10 10 10 10 10 9 9 9 9 7 7 6 6 3 
-1
44
10 10 10 10 10 10 10 10 10 10 10 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 8 8 7 6 6 6 6 6 6 6 5 4 3 3 3 3 
11
10 10 10 10 10 9 8 7 6 6 2 
6
10 10 10 10 8 3 
18
10 10 10 10 10 10 8 8 8 8 7 7 7 6 5 3 2 2 
-1
-1
1
1 
-1
-1
-1
20
10 10 10 10 10 10 10 10 10 9 8 8...

result:

ok 16344 lines

Test #5:

score: 0
Accepted
time: 85ms
memory: 17884kb

input:

10000
18 16 16
1 2 3 4 5 6 7 8 10 11 12 13 14 16 17 18 19 20
2 2 2 1 2 1 1 2 2 2 2 1 2 2 1 2 1 1
403 3 7
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 58 59 60 61 62 63 64 65 66 67 68 ...

output:

-1
126
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
-1
-1
-1
1
1 
-1
-1
10
2 2 2 2 2 2 1 1 1...

result:

ok 16420 lines

Test #6:

score: 0
Accepted
time: 85ms
memory: 17848kb

input:

10000
251 1 1
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

251
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok 16925 lines

Test #7:

score: 0
Accepted
time: 201ms
memory: 29452kb

input:

100
23882 222 481
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

102
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19...

result:

ok 167 lines

Test #8:

score: 0
Accepted
time: 105ms
memory: 26492kb

input:

100
3789 29850 70419
774 1032 1649 1723 2194 3021 3114 3308 3344 3360 3688 3781 3967 4245 4878 4966 5099 5597 5617 5638 5645 5784 5871 6136 6158 6358 6483 6600 6766 6775 6800 6895 7119 7439 7485 7696 7734 8432 8493 8581 8627 9203 9576 9885 10062 10290 10454 10466 10537 10717 10861 11048 11484 11497 ...

output:

30
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19 18 3 
-1
-1
-1
4
20 20 18 10 
-1
6
20 20 20 20 15 9 
-1
-1
5
20 20 20 18 4 
4
20 20 13 7 
-1
4
20 20 19 18 
-1
-1
-1
-1
2
16 8 
-1
3
20 20 6 
8
20 20 20 20 20 20 15 12 
-1
-1
-1
17
20 20 20 20 20 20 20 20 20 20 20...

result:

ok 139 lines

Test #9:

score: 0
Accepted
time: 174ms
memory: 26360kb

input:

100
181 1947 1967
17 23 47 53 55 68 84 92 110 147 153 164 191 198 207 209 215 221 255 269 275 302 305 322 324 363 370 373 385 405 407 429 451 458 466 472 478 500 508 544 557 561 564 565 569 587 600 610 617 630 645 659 665 670 674 715 726 744 747 764 769 770 774 782 786 787 794 795 824 852 860 873 87...

output:

-1
-1
-1
12
10 10 10 10 10 10 10 10 10 10 9 4 
12
10 10 10 10 10 10 10 10 10 10 5 5 
13
10 10 10 10 10 10 10 10 10 10 10 5 4 
-1
22
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 2 
215
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

result:

ok 166 lines

Test #10:

score: 0
Accepted
time: 182ms
memory: 30204kb

input:

100
5589 851 904
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

-1
267
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

result:

ok 184 lines

Test #11:

score: -100
Runtime Error

input:

100
6944 1905 1926
2 3 4 6 7 8 9 10 11 13 15 16 17 18 20 22 23 24 25 29 31 32 33 34 35 39 40 42 43 44 45 46 47 49 51 54 55 57 58 60 61 62 63 64 67 68 69 71 72 74 75 76 78 79 80 81 82 83 84 85 86 90 91 92 94 95 96 98 100 104 105 106 107 108 109 111 112 117 118 119 120 123 125 126 127 128 131 133 134 ...

output:


result: