#include "choreography.h"
#include <vector>
// Global variables to hold the state using dual array approach
int N_dancers;
std::vector<int> initial_p; // initial_p[initial_pos] = dancer_id (kept for compatibility)
std::vector<int> initial_pos; // initial_pos[dancer_id] = initial_pos (kept for compatibility)
// Dual array representation:
std::vector<int> pos_dancers; // pos_dancers[dancer] = position (where is dancer D?)
std::vector<int> pos_positions; // pos_positions[position] = dancer (who is at position P?)
int shift_s; // Global shift for lazy evaluation
// Helper to get actual position with shift applied
int actual_position(int base_pos) {
return (base_pos + shift_s + N_dancers) % N_dancers;
}
// Helper to get actual dancer at position with shift applied
int actual_dancer_at(int pos) {
int base_pos = (pos - shift_s + N_dancers) % N_dancers;
return pos_positions[base_pos];
}
// Initializes the state.
void init(int N, std::vector<int> P) {
N_dancers = N;
initial_p.resize(N);
initial_pos.resize(N);
pos_dancers.resize(N);
pos_positions.resize(N);
for (int i = 0; i < N; ++i) {
initial_p[i] = P[i];
initial_pos[P[i]] = i;
}
// Initialize dual arrays
for (int i = 0; i < N; ++i) {
int dancer = P[i];
pos_positions[i] = dancer; // Position i has dancer
pos_dancers[dancer] = i; // Dancer is at position i
}
shift_s = 0;
}
// Adds a move of type 1 (move right by K). This is O(1).
void move_right(int K) {
shift_s = (shift_s + K) % N_dancers;
}
// Adds a move of type 2 (move left by K). This is O(1).
void move_left(int K) {
shift_s = (shift_s - K + N_dancers) % N_dancers;
}
// Helper function to "bake" the current shift into both arrays
void bake_shift() {
if (shift_s == 0) return; // No need to bake if there's no shift
std::vector<int> new_pos_dancers(N_dancers);
std::vector<int> new_pos_positions(N_dancers);
// Bake shift into pos_dancers
for (int d = 0; d < N_dancers; ++d) {
new_pos_dancers[d] = actual_position(pos_dancers[d]);
}
// Bake shift into pos_positions
for (int p = 0; p < N_dancers; ++p) {
new_pos_positions[p] = actual_dancer_at(p);
}
pos_dancers = new_pos_dancers;
pos_positions = new_pos_positions;
shift_s = 0; // Reset the shift after baking
}
// Adds a move of type 3 (swap adjacent). This is O(N).
void swap_places() {
// First, bake the current shift into both arrays
bake_shift();
// Apply swap to both arrays consistently
for (int i = 0; i < N_dancers; i += 2) {
if (i + 1 < N_dancers) {
// Swap positions i and i+1
int dancer_at_i = pos_positions[i];
int dancer_at_i1 = pos_positions[i + 1];
// Update pos_positions
pos_positions[i] = dancer_at_i1;
pos_positions[i + 1] = dancer_at_i;
// Update pos_dancers
pos_dancers[dancer_at_i] = i + 1;
pos_dancers[dancer_at_i1] = i;
}
}
}
// Adds a move of type 4 (move around). This is O(N) when there's a shift, O(1) when no shift.
void move_around() {
// We need to bake the shift first, then apply move_around logic
bake_shift();
// Now that shift is baked, we can apply the move_around rule:
// For each dancer D, new position = pos_positions[D]
std::vector<int> new_pos_dancers(N_dancers);
for (int dancer = 0; dancer < N_dancers; ++dancer) {
new_pos_dancers[dancer] = pos_positions[dancer];
}
// Update pos_positions to reflect the new arrangement
std::vector<int> new_pos_positions(N_dancers);
for (int dancer = 0; dancer < N_dancers; ++dancer) {
int new_pos = new_pos_dancers[dancer];
new_pos_positions[new_pos] = dancer;
}
pos_dancers = new_pos_dancers;
pos_positions = new_pos_positions;
// shift_s is already 0 from bake_shift()
}
// Returns the current position of dancer D. This is O(1).
int get_position(int D) {
return actual_position(pos_dancers[D]);
}
