QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167921#6400. Game: CelesteqzzyqWA 196ms14820kbC++143.3kb2023-09-07 18:23:462023-09-07 18:23:47

Judging History

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

  • [2023-09-07 18:23:47]
  • 评测
  • 测评结果:WA
  • 用时:196ms
  • 内存:14820kb
  • [2023-09-07 18:23:46]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
mt19937 rnd(time(0));
int n,L,R;
int q[maxn],head,tail;
int a[maxn],c[maxn];
unsigned val[maxn];
int root[maxn],cnt,fl[maxn];
struct yyy{
	int ls,rs,siz;
	unsigned sum;
}f[maxn*20];
int Update(int l,int r,int pre,int k) {
	int rt=++cnt;f[rt]=f[pre];
	if (l==r) return f[rt].siz++,f[rt].sum+=val[k],rt;
	int mid=l+r>>1;
	if (k<=mid) f[rt].ls=Update(l,mid,f[rt].ls,k);
	else f[rt].rs=Update(mid+1,r,f[rt].rs,k);
	f[rt].sum=f[f[rt].ls].sum^f[f[rt].rs].sum;
	f[rt].siz=f[f[rt].ls].siz+f[f[rt].rs].siz;
	return rt;
}
bool find(int l,int r,int rt1,int rt2) {
	if (l==r) return f[rt1].siz>f[rt2].siz;
	int mid=l+r>>1;
	if (f[f[rt1].rs].sum==f[f[rt2].rs].sum) return find(l,mid,f[rt1].ls,f[rt2].ls);
	else return find(mid+1,r,f[rt1].rs,f[rt2].rs);
}
int Query(int l,int r,int rt,int k) {
	if (!f[rt].siz) return 0;
	if (l==r) return l;
	int mid=l+r>>1;
	if (r<=k) {
		if (f[f[rt].rs].siz) return Query(mid+1,r,f[rt].rs,k);
		else return Query(l,mid,f[rt].ls,k);
	}
	int tmp1=0,tmp2=0;
	if (mid<k) tmp1=Query(mid+1,r,f[rt].rs,k);
	if (tmp1) return tmp1;
	tmp2=Query(l,mid,f[rt].ls,k);
	return tmp2;
}
bool cmp(int x,int y) {
	return find(1,n,root[x],root[y]);
//	int id=find(1,n,root[x],root[y]);
//	int tmp1=Query(1,n,root[x],id);
//	int tmp2=Query(1,n,root[y],id);
//	return tmp1>tmp2;
}
void print(int l,int r,int rt) {
//	gdb(l,r,f[f[rt].ls].siz,f[f[rt].rs].siz);
	if (l==r) {
		for (int i=1;i<=f[rt].siz;i++) printf("%d ",l);
		return ;
	}
	int mid=l+r>>1;
	if (f[f[rt].rs].siz) print(mid+1,r,f[rt].rs);
	if (f[f[rt].ls].siz) print(l,mid,f[rt].ls);
}
void solve(void) {
	int i,j,las=0;
	read(n);read(L);read(R);
	for (i=1;i<=n;i++) root[i]=fl[i]=0;cnt=0;
	for (i=1;i<=n;i++) read(c[i]);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) val[i]=rnd();
	root[1]=Update(1,n,root[1],a[1]);
	las=0;
	for (i=2;i<=n;i++) {
		int ls=lower_bound(c+1,c+1+n,c[i]-R)-c;
		int rs=lower_bound(c+1,c+1+n,c[i]-L+1)-c-1;
		if (ls>rs) continue;
		for (j=las+1;j<=rs;j++) {
			while (head<=tail&&cmp(q[tail],j)==0) tail--;
			q[++tail]=j; 
		}
		while (head<=tail&&q[head]<ls) head++;
		las=rs;
		root[i]=Update(1,n,root[q[head]],a[i]);
		fl[i]=1;
	}
	if (fl[n]) printf("%d\n",f[root[n]].siz),print(1,n,root[n]),put();
	else puts("-1");
}
signed main(void){
	int T;read(T);while (T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 13844kb

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: 196ms
memory: 14820kb

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 
26
20 16 16 15 15 14 13 13 12 11 11 8 8 7 7 6 6 5 5 4 4 4 4 4 2 1 
6
6 5 3 2 1 1 
8
19 18 17 11 10 9 7 7 
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...

result:

wrong answer 3rd lines differ - expected: '-1', found: '26'