Submission #103280

#	Time	Username	Problem	Language	Result	Execution time	Memory
103280		figter001	Mechanical Doll (IOI18_doll)	C++17	9 / 100	177 ms	9980 KiB

doll

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 2e5+50;

int n,cnt,at;
vector<int> x,y,a;
bool g[nax];

void dfs(int cur){
  if((at == a.size() - 1 && g[0] == 0) || at == a.size())
    return;
  int u = -cur;
  u--;
  if(x[u] == 0){
    x[u] = a[at];
    at++;
    dfs(-1);
  }else if(y[u] == 0){
    y[u] = a[at];
    at++;
    dfs(-1);
  }else if(g[u] == 0){
    g[u] = 1;
    dfs(x[u]);
  }else if(g[u] == 1){
    g[u] = 0;
    dfs(y[u]);
  }
}

void create_circuit(int M, vector<int> A) {
  a = A;
  a.push_back(0);
  a.push_back(0);
  n = a.size();
  if(n == 3){
    answer({1,0},{},{});
    return;
  }
  for(int k=0;k<30;k++){
    if((1<<k) >= n){
      cnt = (1<<k)-1;
      break;
    }
  }
  x.resize(cnt,0);
  y.resize(cnt,0);
  for(int i=0;i<cnt/2;i++){
    x[i] = -((i+1)*2);
    y[i] = -((i+1)*2+1);
  }
  vector<int> C(M+1,-1);
  dfs(-1);
  for(int i=0;i<cnt;i++){
    if(x[i] == 0){
      x[i] = -1;
    }
    if(y[i] == 0){
      y[i] = -1;
    }
    if(i == cnt-1)
      y[i] = 0;
  }
  answer(C, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void dfs(int)':
doll.cpp:16:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if((at == a.size() - 1 && g[0] == 0) || at == a.size())
      |       ~~~^~~~~~~~~~~~~~~
doll.cpp:16:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if((at == a.size() - 1 && g[0] == 0) || at == a.size())
      |                                           ~~~^~~~~~~~~~~

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