Submission #623901

#	Time	Username	Problem	Language	Result	Execution time	Memory
623901		TimDee	Mechanical Doll (IOI18_doll)	C++17	10 / 100	70 ms	11604 KiB

doll

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

int n, maxsz, maxh;
vector<int> c,x,y,a,s;
int cnt=0;

void build(int i, int h) {
  if (h==maxh-1 || cnt==maxsz-1) {x[i]=1e9+7, y[i]=1e9+7; return;}
  y[i]=-(++cnt+1);
  build(cnt,h+1);
  if (cnt==maxsz-1) return;
  x[i]=-(++cnt+1);
  build(cnt,h+1);
}

void create_circuit(int m, vector<int>A) {

  n=A.size();
  c.assign(m+1,-1); c[0]=A[0];
  for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
  int lg=0; int X=n; while (X>>=1) lg++;
  maxsz=n+lg;
  maxh=lg+1;
  x.assign(maxsz,-1);
  y.assign(maxsz,-1);
  s.assign(maxsz,0);
  build(0,0);

  int have=0;
  for(int i=0; i<maxsz; ++i) {
    if (x[i]==1e9+7) have+=2;
  }

  while (have-n) {
    int i=0;
    while (1) {
      if (s[i]) {
        s[i]^=1;
        if (y[i]==1e9+7) {
          y[i]=-1;
          break;
        }
        i=-y[i]-1;
      } else {
        s[i]^=1;
        if (x[i]==1e9+7) {
          x[i]=-1;
          break;
        }
        i=-x[i]-1;
      }
    }
    --have;
  }

  for (auto v:a) {
    int i=0;
    while (1) {
      //cout<<i<<"->"; int ok; cin>>ok;
      if (s[i]) {
        s[i]^=1;
        if (y[i]==1e9+7) {
          y[i]=v;
          break;
        }
        i=-y[i]-1;
      } else {
        s[i]^=1;
        if (x[i]==1e9+7) {
          x[i]=v;
          break;
        }
        i=-x[i]-1;
      }
    }
  }

  for(int i=0; i<maxsz; ++i) {
    //cout<<-i-1<<" -> ["<<x[i]<<','<<y[i]<<"]\n";
  }

  answer(c,x,y);

}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:22:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   22 |   for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
      |   ^~~
doll.cpp:22:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   22 |   for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
      |                                             ^

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