Contest Results

(Analysis by Benjamin Qi)

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

$$p^K[i]=\overbrace{p[p[\cdots p[i]\cdots]]}^{K\text{ times}}$$

for every $i$. To compute this expression for a single index $i$, first find the minimum positive integer $x$ such that $p^x[i]=i$. We can refer to the sequence

$$i,p[i],p^2[i],\ldots,p^{x-1}[i]$$

Now it is easy to compute $p^K[j]=p^{K\pmod{x}}[j]$ for all $j$ located on the cycle in $O(x)$ time.

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;
  }
}