Submission #1258583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258583		ogkostya	Migrations (IOI25_migrations)	C++20	97.45 / 100	38 ms	1484 KiB

migrations

#include "migrations.h"
#include <cstdio>
#include <stdexcept>
#include <algorithm>

std::vector<std::vector<int>> nn;

int p1[32];
int p2[32];
int p3[32];
int p4[32];
int p5[32];
int d1[10001];
int d2[10001];
int d3[10001];

int left = -1, right = -1;

void pack4(int to, int p[], int count)
{
  int c = to / 63 + 1;
  for (int i = 0; i < count; i++)
    for (int j = i + 1; j < count; j++)
      for (int k = j + 1; k < count; k++)
      {
        c--;
        if (c == 0)
        {
          int rem = to % 63;
          p[i] = rem % 4 + 1;
          rem /= 4;
          p[j] = rem % 4 + 1;
          rem /= 4;
          p[k] = rem % 4 + 1;
          rem /= 4;
          return;
        }
      }
}

int unpack4(std::vector<int> &s, int index, int count)
{
  int c = 0;
  for (int i = 0; i < count; i++)
    for (int j = i + 1; j < count; j++)
      for (int k = j + 1; k < count; k++)
      {
        c++;
        if (s[index + i] != 0 && s[index + j] != 0 && s[index + k] != 0)
        {
          c--;
          c *= 63;
          int x = s[index + k] - 1;
          x = x * 4 + s[index + j] - 1;
          x = x * 4 + s[index + i] - 1;
          return c + x;
        }
      }
  return 0;
}

int pack5(int to, int p[], int count, int w)
{
  int ans = 0;
  for (int i = count - 1; i >= 0; i--)
  {
    p[i] = to % 5;
    if (p[i] != 0)
      ans++;
    to /= 5;
  }
  if (to > 0)
    throw std::runtime_error("A runtime error occurred.");
  return ans;
}

int n;

int repack(int to, int p[], int count, int d[])
{
  int min = count + 1;
  for (int i = 0; i <= n; i++)
  {
    if (d[i] == d[to])
    {
      int cnt = pack5(i, p, count, -1);
      if (min > cnt)
      {
        min = cnt;
        to = i;
      }
    }
  }
  pack5(to, p, count, -1);
  return to;
}

int unpack5(std::vector<int> &s, int index, int count)
{
  int ans = 0;
  for (int i = index, k = 0; k < count; i++, k++)
  {
    ans *= 5;
    ans += s[i];
  }
  return ans;
}

void dfs(int to, int from, int d[])
{
  d[to] = 1 + d[from];
  for (int j : nn[to])
  {
    if (j == from)
      continue;
    dfs(j, to, d);
  }
}

std::pair<int, int> Step(int i)
{
  d1[i] = -1;
  dfs(i, i, d1);
  int m1 = 0;
  for (int j = 0; j <= n; j++)
    if (d1[m1] <= d1[j])
      m1 = j;

  d2[m1] = -1;
  dfs(m1, m1, d2);
  int m2 = 0;
  for (int j = 0; j <= n; j++)
    if (d2[m2] <= d2[j])
      m2 = j;

  d3[m2] = -1;
  dfs(m2, m2, d3);
  int m3 = 0;
  for (int j = 0; j <= n; j++)
    if (d3[m3] <= d3[j])
      m3 = j;

  // printf("%d %d %d\n", m3, m2, m1);
  return std::make_pair(m2, m3);
}

void Change(int i)
{
  d1[left] = -1;
  dfs(left, left, d1);
  if (d1[right] < d1[i])
  {
    right = i;
    return;
  }
  d1[right] = -1;
  dfs(right, right, d1);
  if (d1[left] < d1[i])
  {
    left = i;
    return;
  }
}

int send_message(int N, int i, int Pi)
{
  n = i;
  if (nn.size() == 0)
  {
    nn = std::vector<std::vector<int>>(N, std::vector<int>());
  }
  nn[i].push_back(Pi);
  nn[Pi].push_back(i);

  if (left != -1)
  {
    Change(i);
  }

  if (i == N - 1)
  {
    if (left == i)
    {
      if (right == i - 1)
      {
        return 3;
      }
      else
      {
        return 4;
      }
    }
    else
    {
      if (right == i)
      {
        return 1;
      }
      else if (right == i - 1)
      {
        return 2;
      }
    }
  }
  else if (i == N - 2)
  {
    if (i + 1 - left < 5)
      return i + 1 - left;
  }
  else if (i == N - 3)
  {
    if (i + 1 - right < 5)
      return i + 1 - right;
  }
  else if (i >= N - 5)
  {
    if (i == N - 5)
    {
      if (i + 1 - left < 25)
      {
        pack5(i + 1 - left, p1, 2, 5);
      }
      else
      {
        pack5(0, p1, 2, 5);
      }
    }
    if (left >= N - 5)
    {
      return 0;
    }
    return p1[i - (N - 5)];
  }
  else if (i >= N - 7)
  {
    if (i == N - 7)
    {
      if (i + 1 - right < 25)
      {
        pack5(i + 1 - right, p2, 2, 5);
      }
      else
      {
        pack5(0, p2, 2, 5);
      }
    }
    if (right >= N - 6)
    {
      return 0;
    }
    return p2[i - (N - 7)];
  }
  else if (i >= N - 13)
  {
    if (left > N - 29)
    {
      return 0;
    }
    return p3[i - (N - 13)];
  }
  else if (i >= N - 24)
  {
    if (i == N - 24)
    {
      auto p = Step(i);
      right = p.first;
      pack4(right, p4, 11);
      left = p.second;
      left = repack(left, p3, 6, d3);
    }
    if (right > N - 31)
    {
      return 0;
    }
    return p4[i - (N - 24)];
  }
  return 0;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
  n = S.size();
  int l = -1, r = -1;

  for (int i = n - 1; i >= 0; i--)
  {
    if (i == n - 1)
    {
      if (S[i] == 4)
      {
        l = i;
      }
      else if (S[i] == 3)
      {
        r = i - 1;
        l = i;
      }
      else if (S[i] == 2)
      {
        r = i - 1;
      }
      else if (S[i] == 1)
      {
        r = i;
      }
    }
    if (i == n - 2 && l == -1)
    {
      if (S[i] != 0)
      {
        l = i + 1 - S[i];
      }
    }
    if (i == n - 3 && r == -1)
    {
      if (S[i] != 0)
      {
        r = i + 1 - S[i];
      }
    }
    if (i == n - 5 && l == -1)
    {
      int p = unpack5(S, i, 2);
      if (p != 0)
      {
        l = i + 1 - p;
      }
    }
    if (i == n - 7 && r == -1)
    {
      int p = unpack5(S, i, 2);
      if (p != 0)
      {
        r = i + 1 - p;
      }
    }
    if (i == n - 13 && l == -1)
    {
      l = unpack5(S, i, 6);
    }
    if (i == n - 24 && r == -1)
    {
      r = unpack4(S, i, 11);
    }

    // printf("%d %d %d\n", i, l, r);

    if (l != -1 && r != -1)
      return {l, r};
  }
  return {0, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 67.4511 / 70