Submission #401312

#	Time	Username	Problem	Language	Result	Execution time	Memory
401312		idk321	Mechanical Doll (IOI18_doll)	C++11	47 / 100	415 ms	40300 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int m, n;

vector<int> a;
vector<int> c;
vector<int> x;
vector<int> y;

vector<array<int, 2>> sAt;
int used;

int N;

vector<bool> endNode;
void solve(int ca, int cb, int node)
{

    if (ca == cb)
    {


        endNode[node] = true;
        return;
    }

    int mid = (ca + cb) / 2;
    array<int, 2> cur = {-node * 2, -node * 2 - 1};
    sAt[node] = cur;
    solve(ca, mid, node * 2);
    solve(mid + 1, cb, node * 2+  1);
}


void create_circuit(int M, std::vector<int> A) {
    m = M;
    a = A;
  n = A.size();

  std::vector<int> C(M + 1);
  C[0] = -1;

    N = 1;
    while (N < (n + 1) / 2)
    {
        N *= 2;
    }

    endNode.resize(4 * N);
    sAt.resize(4 * N);
  c = C;
  for (int i = 1; i <= m; i++) c[i] = -1;
    c[0] = a[0];

  used = 1;
    solve(1, N, 1);

   int cur = 1;
   int endNodeNum = 1;
   vector<int> switched(4 * N);
   while (true)
   {
        if (endNode[cur])
        {
            if (endNodeNum == N * 2)
            {
                sAt[cur][1] = 0;
            } else
            {
                if (used < n)
                {
                    sAt[cur][switched[cur]] = a[used];
                    used++;
                    switched[cur] = (switched[cur] + 1) % 2;
                } else
                {
                    sAt[cur][switched[cur]] = -1;
                    switched[cur] = (switched[cur] + 1) % 2;
                }
            }

            if (endNodeNum == N * 2) break;
            cur = 1;
            endNodeNum++;
        } else
        {
            int next = sAt[cur][switched[cur]] * (-1);
            switched[cur] = (switched[cur] + 1) % 2;
            cur = next;
        }
   }


  vector<int> x;
  vector<int> y;

  map<int, int> turnTo;
  set<int> nums;
  nums.insert(-1);
  for (int i = 0; i < 4 *N; i++)
  {
        if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
        {
            if (sAt[i][0] < 0) nums.insert(sAt[i][0]);
            if (sAt[i][1] < 0) nums.insert(sAt[i][1]);


        }
  }
  int cnum = -1;
  for (auto it = nums.rbegin(); it != nums.rend(); it++)
  {
    turnTo[*it] = cnum;
    cnum--;
  }

    for (int i = 0; i < 4 *N; i++)
  {
        if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
        {
            if (sAt[i][0] < 0) x.push_back(turnTo[sAt[i][0]]);
            else x.push_back(sAt[i][0]);
            if (sAt[i][1] < 0) y.push_back(turnTo[sAt[i][1]]);
            else y.push_back(sAt[i][1]);
        }
  }

  answer(c, x, y);
}

/*
2 2
1 2

*/

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