Submission #601503

#	Time	Username	Problem	Language	Result	Execution time	Memory
601503		Belgutei	Mechanical Doll (IOI18_doll)	C++17	6 / 100	73 ms	12092 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define mk make_pair
#define pb push_back

vector<int> v[100005];

int pos, level, tot,i;
int cnt = 0;
vector<int> X, Y, c;
bool ok = 0;

void dfs(int k, int x) {
  if(k == level) {
    if(k == 1) {
      cnt --;
      c[i] = cnt;
    }
    if(pos < v[i].size()) {
      X.pb(v[i][pos]);
      pos ++;
      if(pos < v[i].size()) {
        Y.pb(v[i][pos]);
        pos ++;
      }
      else Y.pb(0);
    }
    else {
      X.pb(0);
      Y.pb(0);
    }
  }
  if(k != level){
    cnt --;
    if(k == 1 && x == 0) c[i] = cnt;
    X.pb(cnt);
    dfs(k + 1, x * 2);
    //
    cnt --;
    Y.pb(cnt);
    //
    dfs(k + 1, x * 2 + 1);
    return;
  }
}

void create_circuit(int M, std::vector<int> A) {
  v[0].pb(A[0]);
  for(i = 0; i < A.size(); i ++) {
    if(i == A.size() - 1) {
      v[A[i]].pb(0);
    }
    else {
      v[A[i]].pb(A[i + 1]);
    }
  }
  c.resize(M + 1);
  //
  for(i = 0; i <= M; i ++) {
    if(v[i].size() == 0) continue;
    if(v[i].size() == 1) {
      c[i] = v[i][0];
      continue;
    }
    for(int j = 1; j <= 20; j ++) {
      if((1 << j) >= v[i].size()) {level = j; break;}
    }
    tot = v[i].size();
    pos = 0;
    ok = 0;
    dfs(1,0);
  }
  //
  // for(auto x: c) cout << x << ' ';
  // cout << '\n';
  // for(auto x: X) cout << x << ' ' ;
  // cout << '\n';
  // for(auto x: Y) cout << x << ' ' ;
  // cout << '\n';
  //
  answer(c,X,Y);
  //
  // int N = A.size();
  // std::vector<int> C(M + 1);
  // C[0] = -1;
  // for (int i = 1; i <= M; ++i) {
  //   C[i] = 1;
  // }
  // std::vector<int> X(N), Y(N);
  // for (int k = 0; k < N; ++k) {
  //   X[k] = Y[k] = A[k];
  // }
  // answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void dfs(int, int)':
doll.cpp:25:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if(pos < v[i].size()) {
      |        ~~~~^~~~~~~~~~~~~
doll.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |       if(pos < v[i].size()) {
      |          ~~~~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(i = 0; i < A.size(); i ++) {
      |              ~~^~~~~~~~~~
doll.cpp:56:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if(i == A.size() - 1) {
      |        ~~^~~~~~~~~~~~~~~
doll.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       if((1 << j) >= v[i].size()) {level = j; break;}
      |          ~~~~~~~~~^~~~~~~~~~~~~~

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