QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106863 | #6400. Game: Celeste | whatever# | WA | 96ms | 19872kb | C++17 | 3.3kb | 2023-05-19 16:15:58 | 2023-05-19 16:18:20 |
Judging History
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 '