Submission #75260

#	Time	Username	Problem	Language	Result	Execution time	Memory
75260		KieranHorgan	Mechanical Doll (IOI18_doll)	C++17	37 / 100	337 ms	68240 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
pair<int, int> exits[400005];
vector<int> X, Y, C;
bool stateIsX[400005];
int depth[400005];
int switchIdx = -1;
set<pair<int, int>> notSetToX;
void build(int cur, int par, int add) {
  if(cur > 0) {
    --switchIdx;
    if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
    else Y[-(par+1)] = switchIdx;
    X.push_back(cur);
    Y.push_back(add);
    depth[-(switchIdx+1)] = depth[-(par+1)]+1;
    stateIsX[-(switchIdx+1)] = 1;
    return;
  }
 
  stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];
  build(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur, add);
}
 
void resetAll(int cur, int par) {
  if(cur == 0) return;
  if(cur > 0) {
    --switchIdx;
    int add = notSetToX.begin()->second;
    // cerr << notSetToX.begin()->first << endl;
    notSetToX.erase(notSetToX.begin());
    if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
    else Y[-(par+1)] = switchIdx;
    X.push_back(cur);
    Y.push_back(add);
    depth[-(switchIdx+1)] = depth[-(par+1)]+1;
    stateIsX[-(switchIdx+1)] = 1;
    resetAll(add, 0);
    return;
  }
 
  if(stateIsX[-(cur+1)]) notSetToX.insert({depth[-(cur+1)], cur});
  else notSetToX.erase({depth[-(cur+1)], cur});
  stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];
 
  resetAll(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur);  
}
 
void create_circuit(int M, vector<int> A) {
  int N = A.size();
 
  if(N == 1) {
    answer({A[0], 0}, {}, {});
    return;
  }
  C.assign(M+1, -1);
 
  X.push_back(A[0]);
  Y.push_back(A[1]);
  stateIsX[0] = 1;
 
  for(int i = 2; i < A.size(); i++) {
    build(-1, 0, A[i]);
  }
 
  for(int i = -1; i >= switchIdx; i--) {
    notSetToX.insert({depth[-(i+1)], i});
  }
  notSetToX.insert({1<<30, 0});
 
  resetAll(-1, 0);
 
  // vector<int> C(M + 1);
  // C[0] = -1;
  // for (int i = 1; i <= M; ++i) {
    // C[i] = -1;
  // }
 
  // for(auto x: A[i]) {
    // build(-1, add);
  // }
 // 
  // for(int i = -1; i >= switchIdx; i--) {
    // X.push_back(exits[-(i+1)].first);
    // Y.push_back(exits[-(i+1)].second);
    // cerr << i << ": " << X[-(i+1)] << " " << Y[-(i+1)] << "  " << stateIsX[-(i+1)] << endl;
  // }
 
 
  // cerr << N << " -> " << X.size() << "   (" << N + log2(N) << ")" << endl;
  // double score;
  // if(X.size() <= N + log2(N)) score = 100;
  // else if(X.size() > 2*N) score = 0;
  // else score = 100*(0.5 + 0.4 * ( (2*N - X.size()) / (N - log2(N)) ) * ( (2*N - X.size()) / (N - log2(N)) ));
  // cerr << "Score: " << score << endl;
 
  // for(int i = 0; i < C.size(); i++)
    // cout << i << " " << C[i] << endl;
  // for(int i = 0; i < X.size(); i++) {
    // cout << -(i+1) << " " << X[i] << endl;
    // cout << -(i+1) << " " << Y[i] << endl;
  // }
 
  answer(C, X, Y);

  // cout << M << endl;
  // for(auto x: A)
    // cout << x << endl;
}

Compilation message (stderr)

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

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