3641. 整数划分（构造）

3641. 整数划分（构造）

试将 1 到 n 这 n 个正整数分成三份，使得这三份的和相等。

Input

输入一个正整数 n (1≤n≤2⋅105)。

Output

输出 n 个正整数 k1,k2,…,kn (1≤ki≤3)，用空格隔开。ki 表示要把 i 这个整数分在第几组。

如果有多解输出任意一解。如果无解输出 ​​Impossible​​。

Examples

input

6

output

3 2 1 1 2 3

input

5

output

1 2 2 1 3

input

7

output

Impossible

题目大概：

1到n这n个整数，问能否分成相等三部分，如果能，那么就输出它输入那个集合。

思路：

构造题，可以看出六个连续的数可以构成一组，能组成相等的三个整数。

然后手动构造出小样例，大样例都是小样例加多个6.

代码：

#include using namespace std;#define ll long longconst int maxn=2e5+100;int vis[maxn];int main(){ int n; scanf("%d",&n); if(n==2||n==3||n%3==1) { printf("Impossible\n"); return 0; } int st; if((n-5)%6==0) { vis[1]=vis[4]=1; vis[2]=vis[3]=2; vis[5]=3; st=6; for(int i=st; i<=n; i=i+6) { vis[i]=1; vis[i+1]=2; vis[i+2]=3; vis[i+3]=3; vis[i+4]=2; vis[i+5]=1; } } if((n-6)%6==0) { vis[1]=vis[6]=1; vis[2]=vis[5]=2; vis[3]=vis[4]=3; st=7; for(int i=st; i<=n; i=i+6) { vis[i]=1; vis[i+1]=2; vis[i+2]=3; vis[i+3]=3; vis[i+4]=2; vis[i+5]=1; } } if((n-8)%6==0) { vis[1]=vis[2]=vis[3]=vis[6]=1; vis[4]=vis[8]=2; vis[5]=vis[7]=3; st=9; for(int i=st; i<=n; i=i+6) { vis[i]=1; vis[i+1]=2; vis[i+2]=3; vis[i+3]=3; vis[i+4]=2; vis[i+5]=1; } } if((n-9)%6==0) { vis[1]=vis[2]=vis[3]=vis[4]=vis[5]=1; vis[6]=vis[9]=2; vis[7]=vis[8]=3; st=10; for(int i=st; i<=n; i=i+6) { vis[i]=1; vis[i+1]=2; vis[i+2]=3; vis[i+3]=3; vis[i+4]=2; vis[i+5]=1; } } for(int i=1; i<=n; i++) { printf("%d ",vis[i]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。