QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112681#6400. Game: Celestedo_while_trueWA 152ms20008kbC++173.5kb2023-06-12 21:25:082023-06-12 21:25:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-12 21:25:12]
  • 评测
  • 测评结果:WA
  • 用时:152ms
  • 内存:20008kb
  • [2023-06-12 21:25:08]
  • 提交

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;
}tree[N*22];
void modify(int u,int &x,int tl,int tr,int p){
	x=++tot;
	tree[x]=tree[u];
	tree[x].sum^=val[p];
	if(tl==tr)return ;
	int mid=(tl+tr)>>1;
	if(p<=mid)modify(ls(u),ls(x),tl,mid,p);
	else modify(rs(u),rs(x),mid+1,tr,p);
}
int cmp(int x,int y,int tl,int tr){//x>y
	if(tree[x].sum==tree[y].sum)return 0;
	if(tl==tr){
		if(tree[x].sum)return 1;
		return 0;
	}
	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};
	tot=0;
	modify(rt[0],rt[1],1,n,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,a[i]);
		}
	}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 19936kb

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: 152ms
memory: 20008kb

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:

wrong answer 10th lines differ - expected: '20 20 20 20 19 19 19 19 18 18 17 17 16 16 13 6 6 3', found: '20 20 20 20 19 19 19 18 18 17 17 16 13 12 6 6 5 3 '