#P18610. Cyclic Shifts
Cyclic Shifts
Cyclic Shifts
给定一个1到n的排列p。一次操作可以选出k>0个下标x1<x2<...<xk,将这些位置的值同时循环右移:x2得到原x1的值,x3得到原x2的值,依此类推,x1得到原xk的值。未选中的位置不变。
选k个位置的名义费用是1/k美元。评测时每次操作的实际费用严格按10^-8乘以ceil(10^8/k)美元计算,也就是将1/k向上取整到小数点后8位。
请给出一种总实际费用不超过2美元的操作方案,将排列变为1,2,...,n。
输入格式
第一行一个整数n。第二行n个整数p1,p2,...,pn,保证它们构成1到n的排列。本题只有一个测试用例。
输出格式
第一行输出非负整数m,表示操作次数。
接下来m行,每行输出一个长度恰为n的二进制字符串。第j个字符为1表示本次选择位置j,为0表示不选。每行必须至少包含一个1。
最终排列必须有序,且按上述向上取整规则计算的总费用不得超过2美元。可以输出任意合法方案;已经有序时允许输出0次操作。
数据范围
1<=n<=5000,1<=pi<=n,所有pi两两不同。
样例输入 1
3
2 1 3
样例输出 1
4
011
110
111
011
样例输入 2
4
1 2 3 4
样例输出 2
0