QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#112684#6400. Game: Celestedo_while_trueWA 84ms20084kbC++173.6kb2023-06-12 21:33:052023-06-12 21:33:07

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:33:07]
  • 评测
  • 测评结果:WA
  • 用时:84ms
  • 内存:20084kb
  • [2023-06-12 21:33:05]
  • 提交

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 '