Submission #1309040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309040		nikaa123	Mechanical Doll (IOI18_doll)	C++20	16 / 100	78 ms	60104 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define deb(x)  cout << #x << " ---> " << x << endl
using namespace std;

// void answer(vector <int> C, vector <int> X, vector <int> Y) {
//     cout << C.size() << endl;
//     for (auto x:C) {
//         cout << x << " " ;
//     }
//     cout << endl;
//     cout << X.size() << endl;
//     for (int i = 0; i < X.size(); i++) {
//         cout << X[i] << " " << Y[i] << endl;
//     }
// }

vector <vector<int>> v(1e6+5);
vector <vector<pair<int,int>>> D(1e6+5);
void dfs(int x, int num,int lim, int d) {
  // deb(x);
  D[(1<<d)].push_back({x,num});
  int lx = x*2;
  int lnum = num;
  if (lx <= lim) {
    dfs(lx, lnum, lim, d+1);
  }
  int rx = x*2+1;
  int rnum = num + (1<<d);
  if (rx <= lim) {
    dfs(rx,rnum,lim,d+1);
  }
}

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

  dfs(1,0,4*M,0);
  for (int i = 1; (1<<i) <= M; i++) {
    sort(D[(1<<i)].begin(),D[(1<<i)].end());
  }


  // for (int i = 0; (1<<i) <= M; i++) {
  //   cout << i << "<---->" << endl;
  //   for (auto [x,ord]:D[(1<<i)]) {
  //     cout << ord << " ";
  //   }
  //   cout << endl;
  // }
  A.push_back(0);
  A.insert(A.begin(),0);
  int N = A.size();
  vector<int> C(M + 1);
  for (int i = 0; i <= M; ++i) {
    C[i] = 1;
  }
  vector<int> X, Y;

  for (int i = 1; i <= N-1; i++) {
    v[A[i-1]].push_back(A[i]);
  }
  int S = 1;
//   cout << 1 << endl;
  for (int i = 0; i <= M; i++) {
    // cout << i << endl;
    int k = v[i].size();
    if (k == 1) {
      C[i] = v[i][0];
    } else if (k > 1) {
        // cout << i << endl;
      int cur = 2;
      vector <int> res;
      C[i] = (0-S);
      res.push_back(S++);
      X.push_back(-1);
      Y.push_back(-1);
      while (cur < k) {
        vector <int> nres;
        for (auto x:res) {
          X[x-1] = (0-S);
          Y[x-1] = (0-(S+1));
          nres.push_back(S);
          nres.push_back(S+1);
          X.push_back(-1);
          Y.push_back(-1);
          X.push_back(-1);
          Y.push_back(-1);
          S+=2;
        }
        cur *= 2;
        res = nres;
      }
      vector <int> id(cur);
      iota(id.begin(),id.end(),0);
      sort(id.begin(),id.end(),[cur](int a, int b) {
        return D[cur][a].second < D[cur][b].second;
      });     

      int xr = cur-k;
      for (int j = 0; j < xr; j++) {
        int ind = id[j];

        if (ind%2==0) {
          int o = ind/2;
          X[res[o]-1] = C[i];
        } else {
          int o = ind/2;
          Y[res[o]-1] = C[i];
        }
        
      }
      for (int j = xr; j < cur; j++) {
        int ind = id[j];

        if (ind%2==0) {
          int o = ind/2;
          X[res[o]-1] = v[i][j-xr];
        } else {
          int o = ind/2;
          Y[res[o]-1] = v[i][j-xr];
        }
      }
      
    }
  }
  
  answer(C, X, Y);
}

// int main () {

//     int n,m;
//     cin >> m;
//     cin >> n;
//     vector <int> a(n);
//     for (int i= 1; i <= n; i++) {
//         cin >> a[i-1];
//     }
//     create_circuit(m,a);


// }

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