Submission #1244520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244520		matan	Choreography (IOI23_choreography)	C++17	7 / 100	1089 ms	6584 KiB

choreography

#include "choreography.h"
#include <vector>

// Global variables to hold the state
int N_dancers;
std::vector<int> initial_p;   // initial_p[initial_pos] = dancer_id
std::vector<int> initial_pos; // initial_pos[dancer_id] = initial_pos

// The transformation state is defined by three components:
// 1. A base permutation `current_f`
// 2. A swap mask `xor_x`
// 3. A cyclic shift `shift_s`
// A dancer who started at an initial position `p` is now at the physical position:
// (current_f[p] ^ xor_x + shift_s) % N
std::vector<int> current_f;
int shift_s;

// Initializes the state.
// Note: The signature is changed to match your choreography.h file.
void init(int N, std::vector<int> P) {
    N_dancers = N;
    initial_p.resize(N);
    initial_pos.resize(N);
    current_f.resize(N);

    for (int i = 0; i < N; ++i) {
        initial_p[i] = P[i];
        initial_pos[P[i]] = i;
    }
    
    // Initially, the transformation is an identity transformation.
    // F[p] = p, no shift, no swap.
    for (int i = 0; i < N_dancers; ++i) {
        current_f[i] = i;
    }
    shift_s = 0;
}

// Adds a move of type 1 (right shift) by lazily updating the shift.
void move_right(int K) {
    // O(1) update
    shift_s = (shift_s + K) % N_dancers;
}

// Adds a move of type 2 (left shift) by lazily updating the shift.
void move_left(int K) {
    // O(1) update. The addition of N_dancers handles potential negative results from subtraction.
    shift_s = (shift_s - K + N_dancers) % N_dancers;
}

// Adds a move of type 3 (swap adjacent). This is now O(N).
void swap_places() {
    // First, bake the current shift into the permutation.
    for (int i = 0; i < N_dancers; ++i) {
        current_f[i] = (current_f[i] + shift_s) % N_dancers;
    }
    shift_s = 0; // Reset the shift.

    // Then, apply the swap to the permutation.
    for (int i = 0; i < N_dancers; ++i) {
        current_f[i] = current_f[i] ^ 1;
    }
}

// Adds a move of type 4. This is the only O(N) operation.
// It "bakes" the lazy transformations (shift and swap) into the base permutation `current_f`.
void move_around() {
    // Step 1: Calculate the current physical state of the board.
    // We create p_current where p_current[dancer_id] = physical_pos.
    std::vector<int> p_current(N_dancers);
    for (int i = 0; i < N_dancers; ++i) {
        int dancer_who_started_at_i = initial_p[i];
        long long base_pos = (long long)current_f[i];
        int physical_pos = (base_pos + shift_s + N_dancers) % N_dancers;
        p_current[dancer_who_started_at_i] = physical_pos;
    }

    // Step 2: Determine the new permutation based on the `move_around` rule.
    // The rule is: new position of dancer `d` is `p_current[d]`.
    std::vector<int> next_f(N_dancers);
    for (int d = 0; d < N_dancers; ++d) {
        int p_init = initial_pos[d]; // The initial position of dancer d
        int new_pos = p_current[d];  // The new physical position for dancer d
        
        // The new logical position for the dancer who started at p_init is new_pos.
        next_f[p_init] = new_pos;
    }

    // Step 3: Update the state.
    // The new base permutation is `next_f`.
    current_f = next_f;
    // Reset the lazy transformations, as their effects are now baked into `current_f`.
    shift_s = 0;
}

// Returns the current position of dancer D.
int get_position(int D) {
    // O(1) calculation by applying the lazy transformations to the base permutation.
    int p_init = initial_pos[D];
    int p_permuted = current_f[p_init];
    // Use long long to prevent overflow before the modulo operation
    long long p_shifted = (long long)p_permuted + shift_s;
    int p_final = (p_shifted % N_dancers + N_dancers) % N_dancers;
    return p_final;
}

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