Submission #586392

#	Time	Username	Problem	Language	Result	Execution time	Memory
586392		wdjpng	Mechanical Doll (IOI18_doll)	C++17	53 / 100	106 ms	21052 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;

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

  vector<vector<int>>to(m+1);
  to[0].push_back(a[0]);
  rep(i,n-1) to[a[i]].push_back(a[i+1]);
  to[a[n-1]].push_back(0);

  vector<vector<int>>ass(19);
  ass[0].push_back(0);
  for(int i = 1; i < 19; i++)
  {
    for(int x : ass[i-1]) { ass[i].push_back(x); ass[i].push_back(x+ass[i-1].size());}

  }
  int s = 0;
  vector<signed>x(400000),y(400000);
  rep(i,m+1)
  {
    if(to[i].size()==0) continue;
    if(to[i].size()==1) {c[i]=to[i][0]; continue;}
    int l = 1;
    while ((1<<l)<to[i].size()) l++;

    int org=-s-1;
    c[i]=org;

    vector<int>cs={s++};
    rep(cl,l-1)
    {
      vector<int>ncs;
      for(int css : cs) {x[css]=-s-1; s++; y[css]=-s-1; s++; ncs.push_back(s-2); ncs.push_back(s-1);}
      cs=ncs;
    }

    int off = (1<<l)-to[i].size();
    rep(j, cs.size())
    {
      rep(k,2)
      {
        int v=org;
        if(ass[l][2*j+k]>=off)
        {
          v = to[i][ass[l][2*j+k]-off];
        }
        if(!k) x[cs[j]]=v;
        else y[cs[j]]=v;
      }
    }
  }

  x.erase(x.begin()+s,x.end());
  y.erase(y.begin()+s,y.end());

  answer(c,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while ((1<<l)<to[i].size()) l++;
      |            ~~~~~~^~~~~~~~~~~~~
doll.cpp:6:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i,n) for(int i = 0; i<n; i++)
......
   47 |     rep(j, cs.size())
      |         ~~~~~~~~~~~~              
doll.cpp:47:5: note: in expansion of macro 'rep'
   47 |     rep(j, cs.size())
      |     ^~~

• 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