Submission #75305

#	Time	Username	Problem	Language	Result	Execution time	Memory
75305		KieranHorgan	Mechanical Doll (IOI18_doll)	C++17	53 / 100	221 ms	20688 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> A, X, Y, C;
int dep[200];
int nextSwitch = -1;
vector<int> AdjList[200005];

int recurseThroughTree(vector<int> b) {
  if(b.size() == 1) return b[0];
  int curSwitch = nextSwitch--;

  // cerr << curSwitch << ": ";
  // for(int i = 0; i < b.size(); i++)
    // cerr << b[i] << " ";
  // cerr << endl;

  vector<int> a;
  for(int i = 0; i < b.size(); i+=2)
    a.push_back(b[i]);
  int l = recurseThroughTree(a);
  a.clear();
  for(int i = 1; i < b.size(); i+=2)
    a.push_back(b[i]);
  int r = recurseThroughTree(a);
  a.clear();
  if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
  X[abs(curSwitch)-1] = l;
  Y[abs(curSwitch)-1] = r;
  // cerr << curSwitch << ": " << l << " " << r << endl;
  return curSwitch;
}

void buildTree(int curTrigger, int curSwitch) {
  int last = AdjList[curTrigger].back();
  AdjList[curTrigger].pop_back();
  while(__builtin_popcount(AdjList[curTrigger].size()+1) != 1) AdjList[curTrigger].push_back(curSwitch);
  AdjList[curTrigger].push_back(last);

  // cerr << curTrigger << ": " << AdjList[curTrigger].size() << endl;
  // cerr << curSwitch << ": ";
  // for(int i = 0; i < AdjList[curTrigger].size(); i++)
    // cerr << AdjList[curTrigger][i] << " ";
  // cerr << endl;
  vector<int> a;
  for(int i = 0; i < AdjList[curTrigger].size(); i+=2)
    a.push_back(AdjList[curTrigger][i]);
  int l = recurseThroughTree(a);
  a.clear();
  for(int i = 1; i < AdjList[curTrigger].size(); i+=2)
    a.push_back(AdjList[curTrigger][i]);
  int r = recurseThroughTree(a);
  a.clear();
  if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
  X[abs(curSwitch)-1] = l;
  Y[abs(curSwitch)-1] = r;
  // cerr << curSwitch << ": " << l << " " << r << endl;
}

void create_circuit(int M, vector<int> A_) {
  A = A_;
  if(!A.empty()) {
    AdjList[0].push_back(A[0]);
    for(int i = 0; i+1 < A.size(); i++) {
      AdjList[A[i]].push_back(A[i+1]);
    }
    AdjList[A.back()].push_back(0);
  }

  C.assign(M+1, 0);
  for(int i = 0; i <= M; i++) {
    if(AdjList[i].empty()) {
    } else if(AdjList[i].size() == 1) {
      C[i] = AdjList[i][0];
    } else {
      C[i] = nextSwitch--;
      buildTree(i, C[i]);
    }
  }

  // cerr << nextSwitch << endl;
  // for(int i = 1; dep[i]; i++)
    // cerr << i << ": " << dep[i] << endl;
  // 
  // cerr << N << " " << X.size() << endl;


  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int recurseThroughTree(std::vector<int>)':
doll.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i = 0; i < b.size(); i+=2)
      |                  ~~^~~~~~~~~~
doll.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i = 1; i < b.size(); i+=2)
      |                  ~~^~~~~~~~~~
doll.cpp:28:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void buildTree(int, int)':
doll.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < AdjList[curTrigger].size(); i+=2)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i = 1; i < AdjList[curTrigger].size(); i+=2)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:55:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i+1 < A.size(); i++) {
      |                    ~~~~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56