Submission #1244767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244767		matan	Choreography (IOI23_choreography)	C++17	19 / 100	1094 ms	7096 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:
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]);
}

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