QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#263788 | #7868. 天空度假山庄 | yyyyxh | 0 | 0ms | 0kb | C++23 | 1.9kb | 2023-11-25 07:30:18 | 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%