#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};
}
