QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263788#7868. 天空度假山庄yyyyxh0 0ms0kbC++231.9kb2023-11-25 07:30:182023-11-25 07:30:18

Judging History

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

  • [2023-11-25 07:30:18]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-11-25 07:30:18]
  • 提交

answer

#include <cstdio>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=1000003,M=223,T=1000003;
const int L=220;
int n,k,m,nn;
bitset<24315> f[M][M];
int seq[T],rk;
void cons(int x,int k,int cur){
	if(!x||!k) return;
	if(cur>=x&&f[x-1][k-1][cur-x]){
		seq[++rk]=x;
		cons(x-1,k-1,cur-x);
		return;
	}
	if(f[x-1][k][cur]){
		cons(x-1,k,cur);
		return;
	}
}
void solve(){
	for(int i=0;i<n;++i){
		int tmp=i;
		for(int j=0;j<k;++j){
			if(!i&&!j) continue;
			if(i==n-1&&j) continue;
			if(j){
				tmp+=seq[j];
				if(tmp>=n) tmp-=n;
			}
			printf("%d ",tmp+1);
		}
	}
	putchar('\n');
}
bitset<24315> g[M];
int main(){
	freopen("sky.in","r",stdin);
	freopen("sky.out","w",stdout);
	n=read();k=read();
	if(k==1){
		for(int i=2;i<=n;++i) printf("%d ",i);
		putchar('\n');
		return 0;
	}
	if(k==2){
		printf("2 3 4 2 ");
		for(int i=4;i<n;++i) printf("%d %d ",i+1,i);
		printf("1 %d \n",n);
		return 0;
	}
	f[0][0].set(0);
	for(int i=1;i<=L;++i){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=i;++j) f[i][j]=f[i-1][j]|(f[i-1][j-1]<<i);
	}
	int pp=(n-1)>>1;
	if(k<=L){
		int ss=min(L,pp);
		for(int i=f[ss][k]._Find_first();i!=int(f[ss][k].size());i=f[ss][k]._Find_next(i))
			if(i%n==1){
				cons(ss,k,i);
				solve();
				return 0;
			}
	}
	for(int t=0;t<=L;++t)
		for(int i=f[L][t]._Find_first();i!=int(f[L][t].size());i=f[L][t]._Find_next(i)) g[t].set(i%n);
	int tmp=1,cnt=0;
	for(int i=pp;i>L&&cnt<k;--i){
		tmp-=i;++cnt;seq[++rk]=i;
		if(tmp<0) tmp+=n;
		if(k-cnt<=L&&g[k-cnt][tmp]){
			int t=k-cnt;
			for(int j=f[L][t]._Find_first();j!=int(f[L][t].size());j=f[L][t]._Find_next(j))
				if(j%n==tmp){
					cons(L,t,j);
					solve();
					return 0;
				}
			assert(0);
		}
	}
	assert(0);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

8216 1

output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #5:

score: 0
Dangerous Syscalls

input:

86132 9

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #16:

score: 0
Dangerous Syscalls

input:

1777 229

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%