oj.uz

답안 #854685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854685 2023-09-28T14:13:05 Z matan Choreography (IOI23_choreography) C++17
29 / 100
 500 ms 6348 KB 
#include <vector>
using namespace std;

  class array_index{
    public:
      int value;
      int base;

      array_index(int value, int base){
        this->base = base;
        this->value = value % this->base;
      }

      array_index(int value){
        this->base = 2;
        this->value = value % this->base;
      }

      array_index(){
        this->base = 2;
        this->value = 0;
      }

      // return int value
      operator int() const { return value; }

      // define the `+` operator
      array_index operator+(const array_index& rhs) const {
        array_index result = *this;     // Make a copy of myself.
        result.value += rhs.value;      // Add the value of the other array_index.
        result.value %= this->base;     // Make sure we stay within bounds.
        return result;                  // Return the result.
      }

      // define the `-` operator
      array_index operator-(const array_index& rhs) const {
        array_index result = *this;     // Make a copy of myself.
        result.value = rhs.value;      // Add the value of the other array_index.
        result.value = (result.value + this->base) % this->base;     // Make sure we stay within bounds.
        return result;                  // Return the result.
      }

      void toggle(){
        this->value = (this->value + 1) % this->base;
      }

      void set_value(int value){
        this->value = value % this->base;
      }
      int get_value(){
        return this->value;
      }


  };

  /**
   * @brief g_array is a 2D array of size 2 x N, where N is the number of dancers/positions.
   * Each row of the vector will display the same choreography but in different manner.
   * One row will display the choreography in terms of dancers, the other in terms of positions.
   * That is, in one vector, each cell represent a postion and the value of the cell is the dancer.
   * I.E. g_array[position_array][0] = 1 means that dancer 1 is in position 0.
   * The other row will display the choreography in terms of dancers, where each cell represent
   * a dancer and the value of the cell is its position.
   * I.E. g_array[dancer_array][3] = 7 means that dancer 3 is in position 7.
   * The rows can switch rules between each other.
   * Two indexes are used to keep track of the current row and the other row.
   * dancer_array is an integer of values 0 or 1, the index is pointing to the row of the dancer notation.
   * position_array is an integer of values 0 or 1, the index is pointing to the row of the position notation.
   * They will never hold the same value at the same time.
   * 
   */
  vector<vector<int>> g_array;

  array_index dancer_array(1);
  array_index position_array(0);

  int NUM_OF_POSITIONS;
  int OFFSET;
  bool TOUCHED_POSITION_ARRAY = false;

  /**
   * @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;
    g_array.resize(2);
    g_array[dancer_array].resize(N);
    g_array[position_array].resize(N);

    for (int i = 0; i < N; i++) {
      g_array[position_array][i] = P[i];
      g_array[dancer_array][P[i]] = i;
    }

    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(OFFSET){
      vector<int> temp = g_array[position_array];
      for (int i = 0; i < NUM_OF_POSITIONS; i++) {
        g_array[dancer_array][i] = (g_array[dancer_array][i] + OFFSET) % NUM_OF_POSITIONS;
        g_array[position_array][(i + OFFSET) % NUM_OF_POSITIONS] = temp[i];
      }
      OFFSET = 0;
    }
    for (int i = 0; i < NUM_OF_POSITIONS / 2; i++)
    {
      int dancer_2i = g_array[position_array][2 * i];
      int dancer_2i_1 = g_array[position_array][2 * i + 1];
      g_array[position_array][2 * i] = dancer_2i_1;
      g_array[position_array][2 * i + 1] = dancer_2i;

      g_array[dancer_array][dancer_2i] = 2 * i + 1;
      g_array[dancer_array][dancer_2i_1] = 2 * i;
    }
    
    return;
  }

  /**
   * @brief This procedure adds a move of type 4 to the sequence of moves.
   *
   */
  void move_around() {
    if(OFFSET){
      vector<int> temp = g_array[position_array];
      for (int i = 0; i < NUM_OF_POSITIONS; i++) {
        g_array[dancer_array][i] = (g_array[dancer_array][i] + OFFSET) % NUM_OF_POSITIONS;
        g_array[position_array][(i + OFFSET) % NUM_OF_POSITIONS] = temp[i];
      }
      OFFSET = 0;
    }
    dancer_array.toggle();
    position_array.toggle();
    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) { 

    return (g_array[dancer_array][D] + OFFSET) % NUM_OF_POSITIONS; 
  }

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 6344 KB Output is correct
2 Correct 65 ms 6340 KB Output is correct
3 Correct 66 ms 6288 KB Output is correct
4 Correct 65 ms 6340 KB Output is correct
5 Correct 43 ms 4544 KB Output is correct
6 Correct 49 ms 4520 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 576 KB Output is correct
6 Correct 5 ms 788 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 6204 KB Output is correct
2 Correct 58 ms 6304 KB Output is correct
3 Correct 57 ms 6348 KB Output is correct
4 Correct 35 ms 4564 KB Output is correct
5 Correct 36 ms 4564 KB Output is correct
6 Correct 36 ms 4564 KB Output is correct

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 6204 KB Output is correct
2 Correct 58 ms 6304 KB Output is correct
3 Correct 57 ms 6348 KB Output is correct
4 Correct 35 ms 4564 KB Output is correct
5 Correct 36 ms 4564 KB Output is correct
6 Correct 36 ms 4564 KB Output is correct
7 Execution timed out 1052 ms 4296 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 6344 KB Output is correct
2 Correct 65 ms 6340 KB Output is correct
3 Correct 66 ms 6288 KB Output is correct
4 Correct 65 ms 6340 KB Output is correct
5 Correct 43 ms 4544 KB Output is correct
6 Correct 49 ms 4520 KB Output is correct
7 Correct 65 ms 6204 KB Output is correct
8 Correct 58 ms 6304 KB Output is correct
9 Correct 57 ms 6348 KB Output is correct
10 Correct 35 ms 4564 KB Output is correct
11 Correct 36 ms 4564 KB Output is correct
12 Correct 36 ms 4564 KB Output is correct
13 Execution timed out 1054 ms 4348 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 6344 KB Output is correct
2 Correct 65 ms 6340 KB Output is correct
3 Correct 66 ms 6288 KB Output is correct
4 Correct 65 ms 6340 KB Output is correct
5 Correct 43 ms 4544 KB Output is correct
6 Correct 49 ms 4520 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 4 ms 576 KB Output is correct
12 Correct 5 ms 788 KB Output is correct
13 Correct 65 ms 6204 KB Output is correct
14 Correct 58 ms 6304 KB Output is correct
15 Correct 57 ms 6348 KB Output is correct
16 Correct 35 ms 4564 KB Output is correct
17 Correct 36 ms 4564 KB Output is correct
18 Correct 36 ms 4564 KB Output is correct
19 Execution timed out 1052 ms 4296 KB Time limit exceeded
20 Halted 0 ms 0 KB -