Submission #237474

#	Time	Username	Problem	Language	Result	Execution time	Memory
237474		A02	Mechanical Doll (IOI18_doll)	C++14	100 / 100	169 ms	13208 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56