QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#112684 | #6400. Game: Celeste | do_while_true | WA | 84ms | 20084kb | C++17 | 3.6kb | 2023-06-12 21:33:05 | 2023-06-12 21:33:07 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n';
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
r=0;bool w=0;char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
int s=1;
while(y){
if(y&1)s=1ll*s*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return s;
}
const int N=1000010;
mt19937_64 rnd(time(NULL)^(ull)(new char));
ull val[N];
int n,L,R;
int rt[N],tot;
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
struct Node{
ull sum;
int lson,rson,ct;
}tree[N*22];
void modify(int u,int &x,int tl,int tr,int p,ull o){
x=++tot;
tree[x]=tree[u];
tree[x].sum^=o;
if(tl==tr){
tree[x].ct++;
return ;
}
int mid=(tl+tr)>>1;
if(p<=mid)modify(ls(u),ls(x),tl,mid,p,o);
else modify(rs(u),rs(x),mid+1,tr,p,o);
}
int cmp(int x,int y,int tl,int tr){//x>y
if(tree[x].sum==tree[y].sum)return 0;
if(tl==tr)return tree[x].ct>tree[y].ct;
int mid=(tl+tr)>>1;
if(tree[rs(x)].sum==tree[rs(y)].sum)return cmp(ls(x),ls(y),tl,mid);
return cmp(rs(x),rs(y),mid+1,tr);
}
#undef ls
#undef rs
int q[N],head,tail;
int p[N];
int ok[N],pre[N];
int a[N],vis[N],rk[N];
void solve(){
read(n,L,R);
for(int i=1;i<=n;i++)ok[i]=pre[i]=rt[i]=vis[i]=0,val[i]=rnd();
for(int i=1;i<=n;i++)read(p[i]);
for(int i=1;i<=n;i++)vis[read(a[i])]++;
for(int i=1;i<=n;i++)vis[i]+=vis[i-1];
for(int i=1;i<=n;i++){
int x=a[i];
rk[vis[x]]=x;
a[i]=vis[x];vis[x]--;
}
for(int i=1;i<=tot;i++)tree[i]={0,0,0,0};
tot=0;
modify(rt[0],rt[1],1,n,rk[a[1]],val[a[1]]);
ok[1]=1;
int pos=0;head=1;tail=0;
for(int i=2;i<=n;i++){
while(p[i]-p[pos+1]>=L){
++pos;
if(ok[pos]){
while(head<=tail && cmp(rt[pos],rt[q[tail]],1,n))--tail;
q[++tail]=pos;
}
}
while(head<=tail && p[i]-p[q[head]]>R)++head;
if(head<=tail){
ok[i]=1;pre[i]=q[head];
modify(rt[q[head]],rt[i],1,n,rk[a[i]],val[a[1]]);
}
}
if(!ok[n])puts("-1");
else{
vi vec;int x=n;
while(x){
vec.pb(x);x=pre[x];
}
cout << vec.size() << '\n';
sort(vec.begin(),vec.end(),[&](const int &x,const int &y){return a[x]>a[y];});
for(auto i:vec)cout << rk[a[i]] << ' ';
puts("");
}
}
signed main(){
#ifdef do_while_true
// assert(freopen("data.in","r",stdin));
// assert(freopen("data.out","w",stdout));
#endif
int T;read(T);
while(T--)solve();
#ifdef do_while_true
// cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 19920kb
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: 84ms
memory: 20084kb
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 16 16 11 10 7 6 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 12...
result:
wrong answer 2nd lines differ - expected: '20 20 19 14 12 11 3', found: '16 16 11 10 7 6 3 '