Submission #854528

#	Time	Username	Problem	Language	Result	Execution time	Memory
854528		matan	Choreography (IOI23_choreography)	C++17	7 / 100	1076 ms	6200 KiB

choreography

#include <vector>

  std::vector<int> POSITIONS;
  std::vector<int> DANCERS;
  int NUM_OF_POSITIONS;
  int OFFSET;
  bool TOUCHED_POSITION_ARRAY = false;

  /**
   * @brief
   *
   */
  void update_dancers_array() {
    for (int i = 0; i < NUM_OF_POSITIONS; i++) {
      DANCERS[POSITIONS[i]] = (OFFSET + i) % NUM_OF_POSITIONS;
    }
    OFFSET = 0;
  }

  /**
   * @brief
   *
   */
  void update_positions_array() {
    if (TOUCHED_POSITION_ARRAY){
      update_dancers_array();
      TOUCHED_POSITION_ARRAY = false;
    }
    for (int i = 0; i < NUM_OF_POSITIONS; i++) {
      POSITIONS[(DANCERS[i] + OFFSET) % NUM_OF_POSITIONS] = i;
    }
    OFFSET = 0;
  }

  /**
   * @brief This procedure is called once at the beginning of the choreography.
   *
   * @param N The number of dancers.
   * @param P Array of length N describing the initial order of the dancers.
   */
  void init(int N, std::vector<int> P) {
    NUM_OF_POSITIONS = N;
    OFFSET = 0;
    for (int i = 0; i < N; i++) {
      POSITIONS.push_back(P[i]);
      DANCERS.push_back(i);
    }
    update_dancers_array();

    return;
  }

  void move_right(int K) {
    OFFSET = (OFFSET + K) % NUM_OF_POSITIONS;
    return;
  }

  void move_left(int K) {
    OFFSET = (OFFSET - K + NUM_OF_POSITIONS) % NUM_OF_POSITIONS;
    return;
  }

  /**
   * @brief This procedure adds a move of type 3 to the sequence of moves.
   *
   */
  void swap_places() {
    if (0 != OFFSET){
      update_positions_array();
    }
    for (int i = 0; i < NUM_OF_POSITIONS / 2; i++) {
      int temp = POSITIONS[2 * i];
      POSITIONS[2 * i] = POSITIONS[2 * i + 1];
      POSITIONS[2 * i + 1] = temp;
    }
    TOUCHED_POSITION_ARRAY = true;
    return;
  }

  /**
   * @brief This procedure adds a move of type 4 to the sequence of moves.
   *
   */
  void move_around() {
    if(0 != OFFSET){
      update_positions_array();
    }
    std::vector<int> temp = POSITIONS;
    for (int i = 0; i < NUM_OF_POSITIONS; i++) {
      POSITIONS[temp[i]] = i;
    }
    TOUCHED_POSITION_ARRAY = true;
    return;
  }

  /**
   * @brief This procedure should return the position of dancer D after performing every move added
   * to the sequence of moves before this call.
   *
   * @param D an integer representing a dancer.
   * @return int
   */
  int get_position(int D) { 
    if (TOUCHED_POSITION_ARRAY){
      update_dancers_array();
      TOUCHED_POSITION_ARRAY = false;
    }
    return (DANCERS[D] + OFFSET) % NUM_OF_POSITIONS; 
  }

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