CF 482A(Diverse Permutation-相邻距离不同数为k的1~n全排列构造)

栏目：互联网时间：2014-11-07 09:10:29

Permutation p is an ordered set of integers p1,???p2,???...,???pn, consisting of n distinct positive integers not larger than n. We'll denote asn the length of permutation p1,???p2,???...,???pn.

Your task is to find such permutation p of length n, that the group of numbers |p1?-?p2|,?|p2?-?p3|,?...,?|pn?-?1?-?pn| has exactly k distinct elements.

Input

The single line of the input contains two space-separated positive integers n, k (1?≤?k?<?n?≤?105).

Output

Print n integers forming the permutation. If there are multiple answers, print any of them.

Sample test(s)

input
3 2

output
1 3 2

input
3 1

output
1 2 3

input
5 2

output
1 3 2 4 5

Note

By |x| we denote the absolute value of number x.

1 10 2 9 3 8 |7 6 5 4 3 2

不同的。。。全为1的

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (100000+10) #define MAXK (100000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,k; int main() { // freopen("CF482A.in","r",stdin); // freopen(".out","w",stdout); cin>>n>>k;k--; int l=1,r=n,b=1; while(l<=r) { if (b) printf("%d",l++); else printf("%d",r--); if (k) b^=1,k--; if (l<=r) putchar(' '); } cout<<endl; return 0; }

------分隔线----------------------------