#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 with pointer swapping capability:
std::vector<int> array1, array2;
std::vector<int>* pos_dancers; // Pointer to current "where is dancer D?" array
std::vector<int>* pos_positions; // Pointer to current "who is at position P?" array
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);
array1.resize(N);
array2.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];
array1[i] = dancer; // Position i has dancer
array2[dancer] = i; // Dancer is at position i
}
// Set up pointers
pos_positions = &array1; // array1[position] = dancer
pos_dancers = &array2; // array2[dancer] = position
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(1) - PURE POINTER SWAP!
void move_around() {
// First bake any pending shifts
bake_shift();
// THE MAGIC: Just swap the pointers! 🪄
// After move_around: new_position[dancer] = old_pos_positions[dancer]
// This means pos_dancers and pos_positions swap roles!
std::swap(pos_dancers, pos_positions);
// That's it! O(1) operation with zero data copying!
}
// Returns the current position of dancer D. This is O(1).
int get_position(int D) {
return actual_position((*pos_dancers)[D]);
}
