CF102268C

贪心构造即可。
具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以及x(贡献是下标比x小且<-x)的数。
贪心地构造,可以保证x只出现一次。暴力枚举检验即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
	scanf("%d%lld",&n,&m);
	for(int i=0;i<=n;++i){
		bckt[i]=0;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		a[p[i]]=-n+i-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&q[i]);
		if(m==0){
			b[q[i]]=n;
		}else if(m>=q[i]-1){
			m-=q[i]-1;
			b[q[i]]=-1;
		}else{
			for(int j=1;j<q[i];++j){
				++bckt[a[j]+n];
			}
			for(int j=1;j<=n;++j){
				bckt[j]+=bckt[j-1];
			}
			for(int j=1;j<q[i];++j){
				if(bckt[a[j]+n]==m){
					m=0;b[q[i]]=-a[j]-1;
					break;
				}
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	puts("");
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}
	puts("");
}
int main(){
	init();
	return 0;
}

发表评论

电子邮件地址不会被公开。