Submission #88319

#	Time	Username	Problem	Language	Result	Execution time	Memory
88319		memikakizaki	Mechanical Doll (IOI18_doll)	C++14	6 / 100	126 ms	14068 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+1;

int n, m;
vector<int> a;
vector<vector<int> > ls;
vector<int> C, X, Y;

int nodes;
int l[N], r[N];
bool state[N];

void gen_adj(int root, int targ_sz) {
  l[root] = r[root] = -1;
  if(targ_sz / 2 >= 2) {
    l[root] = ++nodes;
    gen_adj(l[root], targ_sz / 2);
  }
  if(targ_sz - targ_sz / 2 >= 2) {
    r[root] = ++nodes;
    gen_adj(r[root], targ_sz - targ_sz / 2);
  }
}

void traverse(int root, vector<pair<int,int> > &ord) {
  // cout << root << ' ' << l[root] << ' ' << r[root] << endl;
  if(state[root]) {
    if(r[root] != -1) traverse(r[root], ord);
    else ord.emplace_back(root, 1);
  } else {
    if(l[root] != -1) traverse(l[root], ord);
    else ord.emplace_back(root, 0);
  }
  state[root] ^= 1;
}

pair<int, vector<pair<int,int> > > make_tree(int targ_sz) {
  int root = ++nodes;
  gen_adj(root, targ_sz);
  vector<pair<int,int> > ord;
  // cout << "targ_sz " << targ_sz << endl;
  for(int i = 1; i <= targ_sz; i++) traverse(root, ord);
  // cout << endl;
  // for(auto p: ord) cout << p.first << ' ' << p.second << endl;
  // cout << endl;
  X.resize(nodes);
  Y.resize(nodes);
  return make_pair(root, ord);
}

void create_circuit(int _m, std::vector<int> _a) {
  m = _m, n = _a.size();
  a = _a;
  ls.resize(m+1);
  C.resize(m+1);

  a.insert(a.begin(), 0);
  a.push_back(0);
  for(int i = 0; i <= n; i++) ls[a[i]].push_back(a[i+1]);
  for(int i = 0; i <= m; i++) {
    if(!ls[i].size()) C[i] = 1;
    else if(ls[i].size() == 1) C[i] = ls[i][0];
    else {
      int root;
      vector<pair<int,int> > ord;
      tie(root, ord) = make_tree(ls[i].size());
      C[i] = -root;
      assert(ord.size() == ls[i].size());
      for(int j = 0; j < ord.size(); j++) {
        int idx, tp;
        tie(idx, tp) = ord[j];
        if(tp == 0) X[idx-1] = ls[i][j];
        else Y[idx-1] = ls[i][j];
      }
    }
  }
  // for(int i = 0; i <= m; i++) cout << i << ' ' << C[i] << endl;
  // for(int i = 0; i < X.size(); i++) cout << X[i] <<' ' << Y[i] << endl;
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       for(int j = 0; j < ord.size(); j++) {
      |                      ~~^~~~~~~~~~~~

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