Submission #946678

#	Time	Username	Problem	Language	Result	Execution time	Memory
946678		PagodePaiva	Mechanical Doll (IOI18_doll)	C++17	53 / 100	118 ms	24900 KiB

doll

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

vector <int> g[M];
int c[2*M], x[2*M], y[2*M];
int tp = 1;

void solve(int val, vector <int> &v){
  tp = max(tp, val);
  if(v.size() == 2){
    x[val] = v[0];
    y[val] = v[1];
    return;
  }
  vector <int> a, b;
  for(int i = 0;i < v.size();i++){
    if(!(i % 2)) a.push_back(v[i]);
    else b.push_back(v[i]);
  }
  if(a.size() % 2 != b.size() % 2){
    int t = a.back();
    a.pop_back();
    b.push_back(t);
    a.push_back(-val);
  }
  x[val] = -(val+1);
  solve(val+1, a);
  y[val] = -(tp+1);
  solve(tp+1, b);
  return;
}

void create_circuit(int m, std::vector<int> A) {
  vector <int> a;
  a.push_back(0);
  for(auto x : A) a.push_back(x);
  a.push_back(0);
  for(int i = 0;i < (int) (a.size())-1;i++){
    g[a[i]].push_back(a[i+1]);
  }
  for(int i = 0;i <= m;i++){
    if(g[i].size() == 0){
      c[i] = 0;
      continue;
    }
    if(g[i].size() == 1){
      c[i] = g[i][0];
      continue;
    }
    c[i] = -tp;
    solve(tp, g[i]);
    tp++;
  }
  vector <int> cc, xx, yy;
  for(int i = 0;i <= m;i++) cc.push_back(c[i]);
  for(int i = 1;i < tp;i++){
    xx.push_back(x[i]);
    yy.push_back(y[i]);
  }
  // for(auto t : cc) cout << t << ' ';
  //   cout << endl;
  // for(int i = 0;i < xx.size();i++){
  //   cout << xx[i] << ' ' << yy[i] << endl;
  // }
  answer(cc, xx, yy);
  return;
}

Compilation message (stderr)

doll.cpp: In function 'void solve(int, std::vector<int>&)':
doll.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0;i < v.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