Submission #1244774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244774		matan	Choreography (IOI23_choreography)	C++17	29 / 100	1096 ms	7100 KiB

choreography

#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]);
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 0 / 14
• Subtask 5: 0 / 28
• Subtask 6: 0 / 29