Submission #1239058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239058		mychecksedad	Mechanical Doll (IOI18_doll)	C++20	50.29 / 100	595 ms	43240 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 5e5+100, M = 5010, K = 22;


vi go[N];
void create_circuit(int m, std::vector<int> A) {
  int n = A.size();

  for(int i = 0; i < n; ++i){
    go[A[i]].pb(i + 1 == n ? 0 : A[i + 1]);
  }

  if(n == 1){
    vi X, Y, C;
    C.resize(m + 1);
    C[0] = A[0];
    C[A[0]] = 0;
    answer(C, X, Y);
    return;
  }

  vi C(m + 1);
  vi X(n * 4 + 30, N), Y(n * 4 + 30, N);

  int sz = 1;
  while((1<<sz) < n) ++sz;

  vector<vi> layer(sz + 1);

  int cnt = 1;
  for(int j = 0; j <= sz; ++j){
    for(int i = 0; i < (1<<j); ++i) layer[j].pb(cnt++);
  }
  vi dp(cnt + 5);
  for(int j = cnt-1; j >= cnt-n; --j) dp[j] = 1;
  for(int j = cnt-n-1; j >= 1; --j){
    dp[j] = (j * 2 < cnt ? dp[j * 2] : 0) + (j * 2 + 1 < cnt ? dp[j * 2 + 1] : 0);
  }
  // for(int j = 1; j < cnt; ++j) cerr << j << ' ' << dp[j] << " crap\n";

  // some will be zero, we will erase those...
  C[0] = A[0];
  for(int j = 0; j < n; ++j) C[A[j]] = -layer[0][0];


  vector<pii> av;
  for(int j = cnt-1; j >= cnt-n; --j){
    int val = 0;
    // cerr << j << ' ' << ' ' << sz;
    for(int i = 0; i < sz; ++i) val += ((1<<i)&(j-(1<<(sz)))) ? (1<<(sz-i-1)) : 0;
    av.pb({val, j});
  }
  sort(all(av));

  for(auto [x,y]:av) cerr << x << ' ' << y << '\n';

  vector<bool> dead(cnt, 0);
  for(int j = 1; j * 2 + 1 < cnt; ++j){
    if(dead[j]) continue; 
    // cerr << j << ' ';
    if(dp[j * 2] == 0){
      dead[j * 2] = 1;
      X[j - 1] = -layer[0][0];
    }else{
      X[j - 1] = - 2 * j;
    }
    Y[j - 1] = - 2 * j - 1;
  }
  A.pb(0);
  for(int i = 0; i < n; ++i){
    int x = av[i].ss;
    // cerr << x << ' ';
    if(x % 2) Y[x/2-1] = A[i+1];
    else X[x/2-1] = A[i+1];
  }

  // we gotta compress things

  vector<array<int, 3>> used;
  vi id(X.size());
  for(int i = 0; i < X.size(); ++i){
    if(X[i] != N){
      if(Y[i] == N) Y[i] = -layer[0][0];
      used.pb({i, X[i], Y[i]});
      id[i + 1] = used.size();
    }
  }
  vi xx, yy;
  for(int i = 0; i < (int)used.size(); ++i){
    if(used[i][1] >= 0){
      xx.pb(used[i][1]);
    }else{
      xx.pb(-id[-used[i][1]]);
    }
    if(used[i][2] >= 0){
      yy.pb(used[i][2]);
    }else{
      yy.pb(-id[-used[i][2]]);
    }
    
  }
  for(int &x: C){
    if(x >= 0) x = x;
    else x = -id[-x];
  }

  // cerr << xx.size() << "f\n";

  // X.resize(cnt);
  // Y.resize(cnt);

  // for(int x: xx) cerr << x << ' '; cerr << '\n';
  // for(int x: yy) cerr << x << ' '; cerr << '\n';
  // for(int x: C) cerr << x << ' '; cerr << '\n';

  answer(C, xx, yy);
}

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