First simulate the $M$ reversals in $O(NM)$ (or $O(N+M\log N)$ with a lazy balanced binary search tree, but that is outside the scope of silver). After this, let $p[i]$ denote the $i$-th cow from the right. It suffices to find
As every index of the permutation lies on exactly one cycle, the sum of the cycle lengths is equal to $N$, meaning that this part of the solution runs in $O(N)$ time.
Dhruv Rohatgi's code:
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define MAXN 100000 int N,M,K; int l[100],r[100]; int p[MAXN]; int cc[MAXN]; int pos[MAXN]; vector<int> A[MAXN+1]; int ans[MAXN]; int main() { freopen("swap.in","r",stdin); freopen("swap.out","w",stdout); cin >> N >> M >> K; for(int i=0;i<M;i++) { cin >> l[i] >> r[i]; l[i]--,r[i]--; } for(int i=0;i<N;i++) { p[i] = i; for(int j=0;j<M;j++) if(p[i] >= l[j] && p[i] <= r[j]) p[i] = r[j] + l[j] - p[i]; } int C = 1; for(int i=0;i<N;i++) if(!cc[i]) { cc[i] = C; A[C].push_back(i); int j = p[i]; if(j != i) pos[j] = 1; while(j != i) { A[C].push_back(j); cc[j] = C; if(p[j]!=i) pos[p[j]] = 1 + pos[j]; j = p[j]; } C++; } for(int i=0;i<N;i++) ans[A[cc[i]][(pos[i] + K)%A[cc[i]].size()]] = i; for(int i=0;i<N;i++) cout << ans[i]+1 << '\n'; }
An alternative approach is to use binary exponentiation. Calculate $p^{2^k}[i]$ for each non-negative integer $k$ such that $2^k\le K$, and then combine the appropriate permutations together to get $p^K[k]$. This approach runs in $O(N\log K)$ time.
Nick Wu's code:
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new FileReader("swap.in")); PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("swap.out"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] to = new int[n]; { int[] l = new int[n]; for(int i = 0; i < n; i++) l[i] = i; while(m-- > 0) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()) - 1; int b = Integer.parseInt(st.nextToken()) - 1; while(a < b) { int t = l[a]; l[a] = l[b]; l[b] = t; a++; b--; } } for(int i = 0; i < n; i++) to[i] = l[i]; } int[] ret = new int[n]; for(int i = 0; i < n; i++) ret[i] = i+1; while(k > 0) { if(k%2 == 1) { ret = apply(ret, to); } k /= 2; if(k > 0) to = apply(to, to); } for(int val: ret) pw.println(val); pw.close(); } public static int[] apply(int[] l, int[] op) { int[] ret = new int[l.length]; for(int i = 0; i < ret.length; i++) { ret[i] = l[op[i]]; } return ret; } }