QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291319#5567. Balanced PermutationsCrysfly#RE 0ms0kbC++147.0kb2023-12-26 11:16:372023-12-26 11:16:38

Judging History

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

  • [2023-12-26 11:16:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-26 11:16:37]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f

const ull P[2]={9000000000000000041,9000000000000000053};
ull add(ull x,ull y,ull z){
	return x+y>=z?x+y-z:x+y;
}
ull sub(ull x,ull y,ull z){
	return x<y?x-y+z:x-y;
}
ull mul(ull x,ull y,ull P){
	return (__int128)x*y%P;
	ll s=x*y-(ll)((long double)x*y/P)*P;
	if(s<0)return s+P;
	return (s<P?s:s-P);
}
ull qpow(ull a,ull b,ull P){
	ull c=1;
	for(;b;b>>=1,a=mul(a,a,P))if(b&1)c=mul(c,a,P);
	return c;
}
struct node{
	ull a[2];
	node(ull b=0){a[0]=(b+P[0])%P[0],a[1]=(b+P[1])%P[1];}
	node(ull X,ull Y){a[0]=X,a[1]=Y;}
	ull&operator [](ull b){return a[b];}
	node operator +(node b){return {add(a[0],b[0],P[0]),add(a[1],b[1],P[1])};}
	node operator -(node b){return {sub(a[0],b[0],P[0]),sub(a[1],b[1],P[1])};}
	node operator *(node b){return {mul(a[0],b[0],P[0]),mul(a[1],b[1],P[1])};}
	node inv(){return {qpow(a[0],P[0]-2,P[0]),qpow(a[1],P[1]-2,P[1])};}
	node operator /(node b){return ((*this))*(b.inv());}
	void operator +=(node b){(*this)=(*this)+b;}
	void operator -=(node b){(*this)=(*this)-b;}
	void operator *=(node b){(*this)=(*this)*b;}
	void operator /=(node b){(*this)=(*this)/b;}
	bool isinf(){return a[0]!=a[1];}
};

int n,k1,k2;
int f[maxn],L[maxn],R[maxn];
node g[44],C[44][44];
node fac[44],ifac[44];

int mid0[maxn],mid1[maxn];

int res[maxn];

void solve(int l,int r,int vl,int vr,int op){
	// 0 : small
	// 1 : large
	assert(vr-vl==r-l);
	if(l>r)return;
//	cout<<"solve "<<l<<" "<<r<<" "<<vl<<" "<<vr<<"\n";
	if(op==0){
		int mid=l+mid0[r-l+1];
		res[mid]=vr;
		solve(l,mid-1,vl,vl+(mid-1-l),op);
		solve(mid+1,r,vl+mid-l,vr-1,op);
	}else{
		int mid=l+mid1[r-l+1];
		res[mid]=vr;
		solve(l,mid-1,vr-1-(mid-1-l),vr-1,op);
		solve(mid+1,r,vl,vr-2-(mid-1-l),op);
	}
}

int m,b[42],pos[42];
bool use[42];

int nn;

node dp[42][42][42];
bool vis[42][42][42];

bool ok[42][42];
int suf[42];
node dfs(int l,int r,int k){
	if(!k)return 1;
	if(vis[l][r][k])return dp[l][r][k];
	node &res=dp[l][r][k]=0; vis[l][r][k]=1;
//	cout<<"dfs "<<l<<" "<<r<<" "<<k<<"\n";
	if(use[k]){
		int p=pos[k];
		if((p>=l)&&(!ok[l][p-1]||(p-l<L[r-l+1]||p-l>R[r-l+1])))return /*cout<<"fail "<<l<<" "<<r<<" "<<k<<"\n",*/res;
		return res=dfs(max(p+1,l),r,k-1);
	}
	int cnt=nn-r-suf[k+1];
	if(cnt) res+=dfs(l,r,k-1)*cnt;
	For(p,m+1,r){
		// put k at p
		if(p-l<L[r-l+1] || p-l>R[r-l+1])continue;
		int len=r-p;
		node t=dfs(l,p-1,k-1);
	//	cout<<"l,r,k "<<l<<" "<<r<<" "<<k<<"\n";
	//	cout<<"t: "<<t.a[0]<<" "<<len<<" "<<ifac[len].a[0]<<" "<<g[len].a[0]<<"\n";
		res+=t*ifac[len]*g[len];
	}
//	cout<<"res "<<l<<" "<<r<<" "<<k<<" "<<res.a[0]<<"\n";
	return res;
}
node chk(int n,int m){
//	cout<<"chk "<<n<<" "<<m<<"\n";
//	For(i,1,m)cout<<b[i]<<" "; cout<<" b\n";
	nn=n;
	::m=m;
	memset(vis,0,sizeof vis);
	For(i,1,m)pos[b[i]]=i;
	suf[n+1]=0;
	Rep(i,n,1) suf[i]=suf[i+1]+(!use[i]);
	
	For(i,1,m+1)ok[i][i-1]=1;
	For(len,1,m){
		For(i,1,m-len+1){
			int j=i+len-1,p=i;
			For(k,i,j)if(b[k]>b[p])p=k;
			ok[i][j]=(ok[i][p-1]&&ok[p+1][j]&&(p-i>=L[len]&&p-i<=R[len]));
		}
	}
	node res=dfs(1,n,n);
//	cout<<res.a[0]<<" "<<res.isinf()<<"\n";
	return res;
}

void solve_small(int k){
	cerr<<"solve_small\n";
	if(n<=30){
		if(!g[n].isinf() && k>g[n].a[0]){
			puts("-1");
			return;
		}
	}
	int n=::n;
	int lst=1;
	int nowl=1,nowr=n;
	while(n){
	//	cout<<"n: "<<n<<" "<<lst<<" "<<nowl<<" "<<nowr<<"\n";
		int pos=mid0[n];
		bool ok=0;
		if(n-1-pos>40 || g[n-1-pos].isinf() || g[n-1-pos].a[0]>=k) ok=1;
		if(ok){
	//		cout<<"pos "<<pos<<"\n";
			res[lst+pos]=nowr;
			solve(lst,lst+pos-1,nowl,nowl+pos-1,0);
	//		For(_,1,::n)cout<<res[_]<<" "; cout<<"\n";
			n-=pos+1;
			lst+=pos+1;
			nowl+=pos;
			nowr-=1;
			continue;
		}
		cerr<<"n: "<<n<<" "<<g[n].a[0]<<" "<<k<<"\n";
		assert(n<=40);
		For(i,1,n)use[i]=0;
		For(i,1,n){
			bool qwq=0;
			For(j,1,n) if(!use[j]) {
				b[i]=j; use[j]=1;
				node t=chk(n,i);
				if(t.isinf() || t.a[0]>=k){
					use[j]=qwq=1;
					break;
				}
				k-=t.a[0];
				use[j]=0;
			}
			assert(qwq);
		}
		For(i,1,n) res[lst+i-1]=nowl+b[i]-1;
		break;
	}
	For(i,1,::n) cout<<res[i]<<" "; cout<<"\n";
}

void solve_large(int k){
	cerr<<"solve_large\n";
	if(n<=30){
		if(!g[n].isinf() && k>g[n].a[0]){
			puts("-1");
			return;
		}
	}
	int n=::n;
	int lst=1;
	int nowl=1,nowr=n;
	
	while(n){
	//	cout<<"n: "<<n<<" "<<lst<<" "<<nowl<<" "<<nowr<<"\n";
		int pos=mid1[n];
		bool ok=0;
		if(n-1-pos>40 || g[n-1-pos].isinf() || g[n-1-pos].a[0]>=k) ok=1;
		if(ok){
	//		cout<<"pos "<<pos<<"\n";
			res[lst+pos]=nowr;
			solve(lst,lst+pos-1,nowr-pos,nowr-1,1);
	//		For(_,1,::n)cout<<res[_]<<" "; cout<<"\n";
			n-=pos+1;
			lst+=pos+1;
			nowr-=pos+1;
			continue;
		}
		cerr<<"n: "<<n<<"\n";
		assert(n<=40);
		For(i,1,n)use[i]=0;
		For(i,1,n){
			bool qwq=0;
			Rep(j,n,1) if(!use[j]) {
				b[i]=j; use[j]=1;
				node t=chk(n,i);
				if(t.isinf() || t.a[0]>=k){
					use[j]=qwq=1;
					break;
				}
				k-=t.a[0];
				use[j]=0;
			}
			assert(qwq);
		}
		For(i,1,n) res[lst+i-1]=nowl+b[i]-1;
		break;
	}
	For(i,1,::n) cout<<res[i]<<" "; cout<<"\n";
}

signed main()
{
	freopen("my.out","w",stdout);
	f[1]=1;
	L[1]=R[1]=0;
	g[1]=g[0]=1;
	C[0][0]=1;
	For(i,1,40){
		C[i][0]=1;
		For(j,1,i) C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	fac[0]=ifac[0]=1;
	For(i,1,40)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]/i;
	
	For(i,2,100000){
		f[i]=f[(i-1)/2]+f[i-1-(i-1)/2]+i;
		int l=0,r=(i-1)/2,pos=(i-1)/2;
		while(l<=r){
			int mid=l+r>>1;
			if(f[mid]+f[i-1-mid]+i==f[i])pos=mid,r=mid-1;
			else l=mid+1;
		}
		L[i]=pos,R[i]=i-1-pos;
	//	cout<<i<<" "<<f[i]<<" "<<::l[i]<<" "<<::r[i]<<"\n";
		if(i<=40){
			For(j,L[i],R[i])
				g[i]+=C[i-1][j]*g[j]*g[i-1-j];
	//		cout<<"i: "<<i<<" "<<L[i]<<" "<<R[i]<<" "<<g[i].a[0]<<" "<<g[i].a[1]<<"\n";
		}
	}
	
	mid0[1]=0;
	For(i,2,100000){
		int k=0,up=i/2;
		while((1<<(k+1))<=up) ++k;
		mid0[i]=max((1ll<<k),L[i]);
		mid1[i]=max((1ll<<k)-1,L[i]);
	//	if(i<=500)cout<<"imid: "<<i<<" "<<mid0[i]<<" "<<mid1[i]<<"\n";
	}
	
	n=read(),k1=read(),k2=read();
	solve_small(k1);
	solve_large(k2);
	return 0;
}
/*
1000000000000000000
1825861835980459085

4
1 3 2 4
3 4 1 2
*/

详细

Test #1:

score: 0
Dangerous Syscalls

input:

3 1 2

output:


result: