Submission #1309047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309047		nikaa123	Mechanical Doll (IOI18_doll)	C++20	37 / 100	600 ms	9956 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;
//     }
// }

int rev(int x, int k) {
  int res = 0;
  for (int i = 0; i < k; i++) {
    if (x&(1<<i)) res += (1<<(k-i));
  }
  return res;
}

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

  A.push_back(0);
  int N = A.size();
  vector<int> C(M + 1);
  for (int i = 0; i <= M; ++i) {
    C[i] = -1;
  }
  vector<int> X, Y;

  int k = 0;
  while ((1<<k) < N) {
    k++;
  }
  vector <int> id((1<<k));
  iota(id.begin(),id.end(),0);
  sort(id.begin(),id.end(),[k](int a, int b) {
    return rev(a,k) < rev(b,k);
  });
  int S = 2;
  int cur = 2;
  vector <int> res;
  res.push_back(1);
  X.push_back(-1);
  Y.push_back(-1);
  while (cur < N) {
    vector <int> nres;
    for (auto x:res) {
      X[x-1] = (0-S);
      Y[x-1] = (0-S-1);
      X.push_back(-1);
      Y.push_back(-1);
      X.push_back(-1);
      Y.push_back(-1);
      nres.push_back(S);
      nres.push_back(S+1);
      S += 2;
      cur += 2;
    }
    res = nres;
  }
  int xr = cur - N;
  for (int i = 0; i < xr; i++) {
    int ind = id[i];
    int o = ind/2;
    if (ind%2==0) {
      X[res[o]-1] = -1;
    } else {
      Y[res[0]-1] = -1;
    }
  }
  for (int i = xr; i < cur; i++) {
    int ind = id[i];
    int o = ind/2;
    if (ind%2==0) {
      X[res[o]-1] = A[i-xr];
    } else {
      Y[res[o]-1] = A[i-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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56