CF 286B(Shifting-deque)

1761 ワード

B. Shifting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
John Doe has found the beautiful permutation formula.
Let's take permutation p = p1, p2, ..., pn. Let's define transformation f of this permutation:
k(k(k̵>̵1)は各セグメントの長さである、rはrk̵≦̵nを最大に満たす整数であり、rセグメントと末尾の残りの部分(ある場合)を左にシフト.
シーケンスf(f(...f(p , n - 1), n) .
Input
1行n(2
Output
Print n distinct space-separated integers from 1 to n — a beautiful permutation of size n.
Sample test(s)
input
2

output
2 1 

input
3

output
1 3 2 

input
4

output
4 2 3 1 

Note
A note to the third test sample:
f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
f([1, 4, 2, 3], 4) = [4, 2, 3, 1]
この問題はWJMZBMRの神でシミュレーションしたものです.
まずはdeque<>を普及させて
deque deq;//両端キューの作成
deq.push_back(x) 
deq.push_front(x) 
deq.pop_back(x) 
deq.pop_back(x) 
そしてシミュレーションすることができて、毎回各セグメントの最後を運ぶことができます.
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (1000000+10)
deque deq;
int n;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) deq.push_back(i);
	for (int i=2;i<=n;i++)
	{
		int l=(n-1)/i*i;deq.push_back(deq[l]);
		while (l-i>=0)		
		{
			deq[l]=deq[l-i];
			l-=i;
		}
		deq.pop_front();		
	}	
	for (int i=0;i