Submission #542814

#	Time	Username	Problem	Language	Result	Execution time	Memory
542814		Sho10	Mechanical Doll (IOI18_doll)	C++17	100 / 100	128 ms	13140 KiB

doll

#include "doll.h"
#include <iostream>
#include <vector>
 
#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
 
int const nmax = 400000;
int leftp[1 + nmax];
int rightp[1 + nmax];
int cng[1 + nmax];
 
int switches = 0, added = 0;
 
int creategraph(int nodes, int realnodes){
  if(realnodes == 0)
    return -1;
 
  if(nodes == 1)
    return (added++);
 
  int central = -(++switches);
 
  leftp[-central] = creategraph(nodes / 2, realnodes - MIN(nodes / 2, realnodes));
  rightp[-central] = creategraph(nodes / 2, MIN(nodes / 2, realnodes));
  return central;
}
 
std::vector<int> dest;
 
int real[1 + nmax];
 
int dfs(int node){
  if(0 <= node)
    return node;
  else{
    cng[-node] = !cng[-node];
    if(cng[-node] == 1)
      return dfs(leftp[-node]);
    else
      return dfs(rightp[-node]);
  }
}
 
void create_circuit(int M, std::vector<int> A) {
 
  int N = A.size();
  std::vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i)
    C[i] = -1;
 
  for(int i = 0; i < A.size(); i++)
    dest.push_back(A[i]);
  dest.push_back(0);
  int nodes = 1;
  while(nodes < dest.size())
    nodes *= 2;
 
  creategraph(nodes, dest.size());
 
  for(int i = 0; i < dest.size(); i++)
    real[dfs(-1)] = dest[i];
 
  std::vector<int> X(switches), Y(switches);
 
  for (int k = 1; k <= switches; ++k) {
    X[k - 1] = leftp[k];
    Y[k - 1] = rightp[k];
 
    if(0 <= X[k - 1])
      X[k - 1] = real[X[k - 1]];
    if(0 <= Y[k - 1])
      Y[k - 1] = real[Y[k - 1]];
  }
 
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   while(nodes < dest.size())
      |         ~~~~~~^~~~~~~~~~~~~
doll.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i < dest.size(); i++)
      |                  ~~^~~~~~~~~~~~~
doll.cpp:48:7: warning: unused variable 'N' [-Wunused-variable]
   48 |   int N = 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