C. Strange Sorting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle... Let's have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d - 1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division byd, their relative order after the sorting shouldn't be changed. The string is zero-indexed. For example, for string 'qwerty':
Its 1-sorting is the string 'qwerty' (all characters stand on 0 positions),
Its 2-sorting is the string 'qetwry' (characters 'q', 'e' and 't' stand on 0 positions and characters 'w', 'r' and 'y' are on 1 positions),
Its 3-sorting is the string 'qrwtey' (characters 'q' and 'r' stand on 0 positions, characters 'w' and 't' stand on 1 positions and characters 'e' and 'y' stand on 2 positions),
Its 4-sorting is the string 'qtwyer',
Its 5-sorting is the string 'qywert'.
You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments k andd and transforms string S as follows. For each i from 0 to n - k in the increasing order we apply the operation of d-sorting to the substringS[i..i + k - 1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.
After each shuffling operation you need to print string S.
Input
The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.
The second line of the input contains integer m – the number of shuffling operations (1 ≤ m·n ≤ 106).
Following m lines contain the descriptions of the operations consisting of two integers k and d (1 ≤ d ≤ k ≤ n).
Output
After each operation print the current state of string S.
Sample test(s)
qwerty
3
4 2
6 3
5 2 qertwy
qtewry
qetyrw Note
Here is detailed explanation of the sample. The first modification is executed with arguments k = 4, d = 2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:
qwerty → qewrty → qerwty → qertwy
Thus, string S equals 'qertwy' at the end of first query.
The second modification is executed with arguments k = 6, d = 3. As a result of this operation the whole string S is replaced by its 3-sorting:
qertwy → qtewry
The third modification is executed with arguments k = 5, d = 2.
qtewry → qertwy → qetyrw
因為我們知道 每次進來一個點 就有一個點 出去 ， 這裡面可能存在 有些點一直在這個區間中，然後我們可以知道最後進來的那個點出了步數不夠，其他情況下一定能夠出來，那麼我們從這個最後一個點出發模拟出他的最後出去的路徑，然後可以發現不再這個路徑上的點一定是循環再這個區間内， 因為 每次進來的 一個數必将會出去，那麼出去又是在這條路徑上，于是他們就一定不能出去了，這樣把他們的循環節路徑一一記下來，那麼就下來的工作就剩下枚舉每個點 然後求出他們的最後輸出在哪裡就可以了，因為對于k-1及以後點點 可以通過目前位置和剩下位置，在路徑上找出最後的 位置
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
char str[2][1000005];
int k,d,n,len,tim;
int R[1000005],ge;
int RFE[1000005],RE[1000005];
vector<int> F[10000005];
void solve(int st, int loc){
int G=k/d;
int H=k%d;
while(loc!=0){
RFE[loc]=1;
int rr=loc%d;
int num=rr*G;
if(H!=0){
if( H<rr) num+=H;
else num+=rr;
}
num+=loc/d;
loc=num-1;
R[ge]=loc;
RE[loc]=ge++;
}
}
void xunhun(int nu, int loc){
F[nu].clear();
int G=k/d;
int H=k%d;
int rw=0;
while(RFE[loc]==0){
F[nu].push_back(loc);
RFE[loc]=nu;
RE[loc]=rw++;
int rr=loc%d;
int num=rr*G;
if(H!=0){
if( H<rr ) num+=H;
else num+=rr;
}
num+=loc/d;
loc=num-1;
}
}
void inti(int k){
for(int i=0; i<=k; ++i) RFE[i]=0;
}
int main()
{
while(scanf("%s",str[0])==1){
len = strlen(str[0]);
scanf("%d",&n);
int now=0;
for(int i=0; i<n; ++i){
now=1-now;
scanf("%d%d",&k,&d);
inti(k);
ge=0;
tim=len-k+1;
str[now][0]=str[1-now][0];
solve(0,k-1);
for(int j=k-1; j<len; ++j){
int loc;
if( len-j >= ge ) loc=R[ge-1]+j-k+1+ge;
else loc = R[len-j-1]+j-k+1+len-j;
str[now][loc]=str[1-now][j];
}
int nu=2;
for(int j=1; j<k-1; ++j)if(RFE[j]==0){
xunhun(nu,j); nu++;
}
for(int j=1; j<k-1; ++j)
if(RFE[j]==1){
if(tim>=ge-RE[j]) str[now][ ge-RE[j]-1 ]=str[1-now][j];
else str[now][R[RE[j]+tim]+tim]=str[1-now][j];
}else{
int sz=F[RFE[j]].size();
int ddd = F[ RFE[j] ][ (RE[j]+tim%sz)%sz ];
int loc = tim+ddd;
str[now][loc]=str[1-now][j];
}
str[now][len]=0;
printf("%s\n",str[now]);
}
}
return 0;
} View Code