agc046_e Permutation Cover

https://atcoder.jp/contests/agc046/tasks/agc046_e

Tutorial

https://img.atcoder.jp/agc046/editorial.pdf

称序列中每个元素都在某个作为排列的区间中为性质1

考虑什么时候才有解.

对于单独两个元素(a_x,a_y)分析,若(a_x>2a_y),那么发现一定存在某个(x),距离左右的边界或(x)之间都没有(y).

也就是说对于最大值(a_x)和最小值(a_y),(a_x le 2a_y)是有解的必要条件.

考虑如果满足这个条件如何构造一组解,发现对于任意(Sin[K]),一定存在一种序列使得(S)中的元素出现了二次,([K]setminus S)的元素出现了一次,且满足性质1.那么就可以这样分为若干组以上面的条件为指导构造出一组解来.

所以(a_x le 2a_y)是有解的充要条件.

考虑贪心的增量构造,设现在的序列为(P),且(|P|ge K),满足性质1.考虑怎样的(P)是合法(即可以成为某个解的前缀)的.

和上面类似的考虑,设(b_i)表示剩下的序列中还需要(i)出现多少次,而且由于(P)的存在相当于左边界的条件有所改变,所以

设(x,y)分别为(b)的最大值和最小值,则(xle 2y+1)
若(x=2y+1),则(P)的结尾的(K)个元素,称其为排列(Q),满足所有(b_i=x)的元素在(b_i=y)的元素之前

证明必要和充分的过程和上面类似.

此时由于我们需要(P)时刻满足性质1,所以不能像一般增量法一样一个个添加元素.我们枚举添加的元素个数(m),我们要添加的元素要和(P)结尾的(K-m)个元素组成排列,且需要满足上述(P)合法的条件.对于每个(m),我们可以贪心得到字典序最小的增加的元素的排列或判断其无解.然后对于合法的所有排列,选择字典序最小的加入(P).

对于每个(m),贪心的复杂度是(O(K)),总时间复杂度(O(K^2 sum a_i))

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char gc() {
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void rd(T &x) {
	x=0; int f=1,ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=gc();}
	x*=f;
}
const int maxK=100+5,maxn=1000+5;
int n,K,a[maxK],an[maxn];
bool vis[maxK];
inline bool cmp(const vector<int> &a,const vector<int> &b) {
	for(int i=0;i<a.size()&&i<b.size();++i) if(a[i]!=b[i]) return a[i]<b[i];
	return a.size()<b.size();
}
void fail(vector<int> &re) {
	for(int i=0;i<=K;++i) re.push_back(K+1);
}
void sol(int s,int m,vector<int> &re) {
	static int b[maxK]; memcpy(b,a,sizeof(b));
	memset(vis,0,sizeof(vis));
	for(int i=1;i+m<=K;++i) vis[an[s-i]]=1;
	for(int i=1;i<=K;++i) if(!vis[i]) {
		if(!b[i]) {fail(re); return;}
		--b[i];
	}
	int x=*max_element(b+1,b+K+1),y=*min_element(b+1,b+K+1);
	if(x>2*y+1) {fail(re); return;}
	vector<int> A,B,C;
	if(x==2*y+1) {
		bool flag=0;
		for(int i=1;i+m<=K;++i) {
			if(b[an[s-i]]==x) flag=1;
			else if(b[an[s-i]]==y) {
				if(flag) {fail(re); return;}
			}
		}
		for(int i=K;i>=1;--i) if(!vis[i]) {
			if(b[i]==x) A.push_back(i);
			else if(b[i]==y) B.push_back(i);
			else C.push_back(i);
		}
	}
	else for(int i=K;i>=1;--i) if(!vis[i]) C.push_back(i);
	for(int i=1;i<=m;++i) {
		if(A.size()) {
			int t=C.size()?C.back():K+1;
			if(A.back()<t) re.push_back(A.back()),A.pop_back();
			else re.push_back(t),C.pop_back();
		}
		else {
			int a=B.size()?B.back():K+1,b=C.size()?C.back():K+1;
			if(a<b) re.push_back(a),B.pop_back();
			else re.push_back(b),C.pop_back();
		}
	}
}
int main() {
	rd(K);
	for(int i=1;i<=K;++i) rd(a[i]),n+=a[i];
	if(*max_element(a+1,a+K+1)>2*(*min_element(a+1,a+K+1))) {puts("-1"); return 0;}
	for(int i=1;i<=n;) {
//		debug("---
");
		vector<int> Q[maxK];
		if(i==1) sol(i,K,Q[1]);
		else {
			for(int j=1;j<=K;++j) sol(i,j,Q[j]);
			int k=1;
			for(int j=2;j<=K;++j) if(cmp(Q[j],Q[k])) k=j;
			if(k!=1) swap(Q[1],Q[k]);
		}
		for(int j=0;j<Q[1].size();++j) an[i+j]=Q[1][j],--a[Q[1][j]];
		i+=Q[1].size();
//		for(int j=1;j<i;++j) debug("%d ",an[j]); debug("
");
	}
	for(int i=1;i<=n;++i) {
		if(i!=1) printf(" ");
		printf("%d",an[i]);
	}
	printf("
");
	return 0;
}