Submission #587138

#	Time	Username	Problem	Language	Result	Execution time	Memory
587138		wdjpng	Mechanical Doll (IOI18_doll)	C++17	12 / 100	97 ms	14624 KiB

doll

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

#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)

using namespace std;

vector<signed>x,y;
int pow2=1;
int cs = 0, ct = 1;
vector<pair<int,int>>ind(2e5+2);
int build(int l, int r, vector<signed>&a)
{
  if(r<=pow2-a.size()) return -1;
  if(l+1==r) return ct++;
  cs++;
  int ccs = -cs; 
  ind[ccs+2e5].first = build(l,(l+r)/2,a); 
  ind[ccs+2e5].second = build((l+r)/2,r,a); 
  return ccs;
}

int cntr = 0;
vector<bool>flip(2e5+2,false);
int sim(int cs, vector<signed>&a)
{
  if(cs>0) return a[cntr++];
  flip[cs+2e5]=!flip[cs+2e5];

  if(flip[cs+2e5]) x[-cs-1]=sim(ind[cs+2e5].first,a);
  else y[-cs-1]=sim(ind[cs+2e5].second,a); 

  return cs;
}

void create_circuit(signed m, vector<signed> a) {
  signed n = a.size();
  vector<signed>c(m+1);

  c[0]=a[0];
  if(n==1)
  {
    c[a[0]]=0;
    return answer(c,{},{});
  }
  a.push_back(0);
  a.erase(a.begin(), a.begin()+1);

  while (pow2<a.size()) pow2*=2;
  
  rep(i,m) c[i+1]=-1;
  build(0,pow2,a);
  x.assign(cs,1e9);
  y.assign(cs,1e9);

  rep(i,n) sim(-1,a);
  answer(c,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'long long int build(long long int, long long int, std::vector<int>&)':
doll.cpp:16:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   16 |   if(r<=pow2-a.size()) return -1;
      |      ~^~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:51:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   while (pow2<a.size()) pow2*=2;
      |          ~~~~^~~~~~~~~

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