oj.uz

Submission #237474

# Submission time Handle Problem Language Result Execution time Memory
237474 2020-06-06T21:53:04 Z A02 Mechanical Doll (IOI18_doll) C++14
100 / 100
 169 ms 13208 KB 
#include "doll.h"
#include<iostream>
#include <vector>

using namespace std;

int big = 1000000;

void create_circuit(int M, std::vector<int> A) {


  int N = A.size();

  std::vector<int> C(M + 1);

  std::vector<int> X, Y;
  vector<int> X1 (2 * N + 10, big);
  vector<int> Y1 (2 * N + 10, big);

  vector<int> switch_row;

  for (int i = 0; i < (N + 2) / 2; i++){
    switch_row.push_back(0);
    X1[i] = -1;
    Y1[i] = -1;
  }

  int current_row_number = 1;
  long long current_row = (N + 2) / 2;

  while (current_row != 1){

    long long last_row = current_row;
    current_row = last_row / 2 + last_row % 2;
    //cout << current_row << ' ' << last_row << endl;

    for(int i = 0; i < last_row / 2 + last_row % 2; i++){
        //cout << ' ' << i << ' ' << switch_row.size() << endl;
        switch_row.push_back(current_row_number);
        Y1[switch_row.size() - 1] = switch_row.size() + i - last_row - 1;
        if (switch_row[switch_row.size() + i - last_row] == current_row_number - 1){
            X1[switch_row.size() - 1] = switch_row.size() + i - last_row;
        }
    }
    current_row_number++;
  }

  int top_switch = switch_row.size() - 1;

  for (int i = 0; i <= M; i++){
    C[i] = -top_switch-1;
  }



  A.push_back(0);
  if ((N + 1) % 2){
    A[A.size() - 1] = -top_switch-1;
    A.push_back(0);
  }
  int current_trigger = 0;
  int current_switch = top_switch;
  vector<int> isY (2 * N + 10, false);

  while (current_trigger < A.size()){
    //cout << current_trigger << ' ' << current_switch << endl;
    if (!isY[current_switch]){
        isY[current_switch] = true;
        if (X1[current_switch] == -1){
            X1[current_switch] = -1-A[current_trigger];
            //cout << 'd' << X1[current_switch] << ' ' << A[current_trigger] << endl;
            current_trigger++;
            current_switch = top_switch;
        } else{
            if (X1[current_switch] == big){
                X1[current_switch] = top_switch;
                current_switch = top_switch;
            } else {
                current_switch = X1[current_switch];
            }
        }
    } else {

        isY[current_switch] = false;
        if (Y1[current_switch] == -1){
            Y1[current_switch] = -1-A[current_trigger];
            //cout << 'e' << X1[current_switch] << ' ' << A[current_trigger] << endl;
            current_trigger++;
            current_switch = top_switch;
        } else{
            if (Y1[current_switch] == big){
                Y1[current_switch] = top_switch;
                current_switch = top_switch;
            } else {
                current_switch = Y1[current_switch];
            }
        }

    }

  }

  int c = 0;
  while (Y1[c] != big){
    //cout << c << endl;
    X.push_back(-1-X1[c]);
    Y.push_back(-1-Y1[c]);
    //cout << X[X.size() - 1] << ' ' << Y[Y.size() - 1] << ' ' << c << endl;
    //cout << ' ' << X1[c] << ' ' << Y1[c] << endl;
    c++;
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while (current_trigger < A.size()){
      |          ~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 51 ms 5580 KB Output is correct
3 Correct 51 ms 5192 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1356 KB Output is correct
6 Correct 72 ms 7424 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 51 ms 5580 KB Output is correct
3 Correct 51 ms 5192 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1356 KB Output is correct
6 Correct 72 ms 7424 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 8688 KB Output is correct
9 Correct 97 ms 9156 KB Output is correct
10 Correct 167 ms 13208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 51 ms 5580 KB Output is correct
3 Correct 51 ms 5192 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1356 KB Output is correct
6 Correct 72 ms 7424 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 8688 KB Output is correct
9 Correct 97 ms 9156 KB Output is correct
10 Correct 167 ms 13208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 132 ms 12724 KB Output is correct
15 Correct 107 ms 8296 KB Output is correct
16 Correct 128 ms 12576 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 138 ms 12952 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 82 ms 8012 KB Output is correct
3 Correct 80 ms 7920 KB Output is correct
4 Correct 123 ms 11956 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 82 ms 8012 KB Output is correct
3 Correct 80 ms 7920 KB Output is correct
4 Correct 123 ms 11956 KB Output is correct
5 Correct 135 ms 12444 KB Output is correct
6 Correct 127 ms 12296 KB Output is correct
7 Correct 130 ms 12312 KB Output is correct
8 Correct 126 ms 12128 KB Output is correct
9 Correct 94 ms 7904 KB Output is correct
10 Correct 159 ms 12060 KB Output is correct
11 Correct 125 ms 11952 KB Output is correct
12 Correct 79 ms 7904 KB Output is correct
13 Correct 87 ms 8092 KB Output is correct
14 Correct 84 ms 8120 KB Output is correct
15 Correct 83 ms 8280 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 79 ms 8228 KB Output is correct
18 Correct 85 ms 8000 KB Output is correct
19 Correct 87 ms 7912 KB Output is correct
20 Correct 122 ms 12072 KB Output is correct
21 Correct 169 ms 11948 KB Output is correct
22 Correct 127 ms 12040 KB Output is correct