Submission #1244831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244831		2288	Mechanical Doll (IOI18_doll)	C++20	47 / 100	45 ms	8972 KiB

doll

#include "doll.h"

using namespace std;

#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;

int rev_bit(int x, int l){
  int y=0;
  for (int i=0;i<l;i++){
    y=y*2+x%2;
    x/=2;
  }
  return y;
}

int ind_to_x(int i){
  return -i-1;
}

int gen(vi& X, vi& Y, vi& dest){
  int n=1,lgn=0;while(n<dest.size())(n*=2),lgn++;
  int xi = X.size()-1;
  vi dest2(n,ind_to_x(xi+1));

  for (int i=0;i+1<dest.size();i++)dest2[rev_bit(i,lgn)]=dest[i];
  dest2[n-1] = dest.back();

  for (int i=1;i<n/2;i++){
    X.pb(ind_to_x(xi+i*2));
    Y.pb(ind_to_x(xi+i*2+1));
  }

  for (int i=0;i<n;i+=2){
    X.pb(dest2[i]);
    Y.pb(dest2[i+1]);
  }
  return ind_to_x(xi+1);
}

void create_circuit(int m, std::vector<int> A) {
  int n = A.size();
  std::vector<int> C(m + 1);

  vi X,Y;
  A.pb(0);
  C[0]=A[0];
  A.erase(A.begin());
  C[1]=gen(X,Y,A);

  for (int i=1;i<=m;i++){
    C[i] = C[1];
  }

  answer(C, X, Y);
}

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