#include "choreography.h"
#include <vector>
#include <numeric>
using namespace std;
/**
* We track two permutations:
* 1. dancer_to_initial_pos: dancer_id -> position at t=0
* 2. initial_pos_to_dancer: position at t=0 -> dancer_id
* * We use two offsets (even_offset, odd_offset) to track how dancers
* who started at even vs odd positions have moved over time.
*/
int total_dancers;
int permutations[2][100005]; // [0]: dancer->pos, [1]: pos->dancer
int active_perm = 0; // Swaps between 0 and 1 when move_around() is called
// Offsets for dancers who started at even positions vs odd positions
int post_move_offset[2] = {0, 0};
int pre_move_offset[2] = {0, 0};
void init(int n, vector<int> P) {
total_dancers = n;
for (int i = 0; i < n; ++i) {
permutations[0][i] = P[i]; // Where dancer i starts
permutations[1][P[i]] = i; // Which dancer starts at position i
}
}
void move_right(int K) {
for (int i = 0; i < 2; ++i) {
post_move_offset[i] = (post_move_offset[i] + K) % total_dancers;
}
}
void move_left(int K) {
// Moving left K is equivalent to moving right N - K
move_right(total_dancers - K);
}
void swap_places() {
for (int i = 0; i < 2; ++i) {
// Determine if this group is currently at an even or odd position
int current_pos = (i + post_move_offset[i]) % total_dancers;
if (current_pos % 2 == 0) {
post_move_offset[i] = (post_move_offset[i] + 1) % total_dancers;
} else {
post_move_offset[i] = (post_move_offset[i] - 1 + total_dancers) % total_dancers;
}
}
}
void move_around() {
// move_around effectively inverts the permutation.
// In terms of our state, we swap our 'current' offsets with our 'pre' offsets
// and toggle which mapping array we use.
active_perm ^= 1;
for (int i = 0; i < 2; ++i) {
swap(post_move_offset[i], pre_move_offset[i]);
}
}
int get_position(int dancer_id) {
// 1. Account for shifts that happened "before" the current inversion state
int parity_group = (dancer_id - pre_move_offset[0] + total_dancers) % 2;
int adjusted_id = (dancer_id - pre_move_offset[parity_group] + total_dancers) % total_dancers;
// 2. Perform the permutation lookup
int pos = permutations[active_perm][adjusted_id];
// 3. Apply the "post-inversion" offsets
int final_pos = (pos + post_move_offset[pos % 2]) % total_dancers;
return final_pos;
}
