Submission #1254422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254422		flashmt	Migrations (IOI25_migrations)	C++20	93.11 / 100	946 ms	13216 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int N = 1e4;
const int Z = 4;
const int POW[] = {1, 4, 16, 64, 256};

const int A = N - 1;
const int B = N - 2;
const int C = N - 3;
const int D = N - 4;

// phase 0: 4 messages in 48 pos (50937665) -> need 1225
// phase 1: 3 messages in 6 pos (1545) -> need 21
// phase 2: 2 messages in 2 pos (25) -> 2 unknown
// phase 3: 2 messages to for final 4 pos
const vector<int> POS = {48, 6, 2, 2};
const int FROM = N - accumulate(begin(POS), end(POS), 0);
const vector<int> MSG = {4, 3, 2, 2};

vector<int> a[N];
int n, u[N], v[N], maxDist, dist[N];
vector<vector<int>> seqs;
vector<int> seq, mess;

void gen(int i, int pos, int msg, int last)
{
  seqs.push_back(seq);
  if (i == msg)
    return;
  for (int x = last + 1; x < pos; x++)
  {
    seq.push_back(x);
    gen(i + 1, pos, msg, x);
    seq.pop_back();
  }
}

void dfs(int x)
{
  for (int y : a[x])
    if (dist[y] < 0)
    {
      dist[y] = dist[x] + 1;
      dfs(y);
    }
}

vector<int> toMessage(int value, int len)
{
  vector<int> mes(len);
  for (auto seq : seqs)
  {
    int sz = size(seq);
    if (value >= POW[sz]) value -= POW[sz];
    else
    {
      for (int id : seq)
      {
        mes[id] = value % Z + 1;
        value /= Z;
      }
      return mes;
    }
  }

  assert(0);
  return {};
}

int fromMessage(vector<int> ids, vector<int> vals)
{
  int value = 0;
  for (auto seq : seqs)
    if (seq != ids) value += POW[size(seq)];
    else
    {
      for (int i = 0; i < size(seq); i++)
        value += (vals[i] - 1) * POW[i];
      return value;
    }

  assert(0);
  return 0;
}

int getPhase0Value(int i)
{
  if (u[i] > v[i])
    swap(u[i], v[i]);
  return (n - 1 + n - u[i]) * u[i] / 2 + (v[i] - u[i] - 1);
}

pair<int, int> fromPhase0Value(int value)
{
  int u = 0, v = 0;
  while (value >= n - 1 - u)
  {
    value -= n - 1 - u;
    u++;
  }
  v = u + 1 + value;
  return {u, v};
}

int match(int x, int y, int xx, int yy)
{
  return (x == xx && y == yy) || (x == yy && y == xx);
}

int getPhase12Value(int from, int to) // [from, to]
{
  int value = 0;
  for (int j = from; j < to; j++)
    for (int k = j + 1; k <= to; k++)
    {
      if (match(u[to], v[to], j, k))
        return value; // x, y
      value++;
    }

  for (int j = from; j <= to; j++)
  {
    if (u[to] == j)
      return value; // x, _
    value++;
    if (v[to] == j)
      return value; // _, x
    value++;
  }

  return value; // _, _
}

pair<int, int> fromPhase12Value(int value, int from, int to, int u, int v) // [from, to]
{
  for (int j = from; j < to; j++)
    for (int k = j + 1; k <= to; k++)
    {
      if (value == 0)
        return {j, k};
      value--;
    }

  for (int j = from; j <= to; j++)
  {
    if (value == 0)
      return {j, v};
    value--;
    if (value == 0)
      return {u, j};
    value--;
  }

  return {u, v};
}

int send_message(int _, int i, int Pi) {
  n = N;
  if (i == 1)
    u[0] = v[0] = maxDist = 0;
  a[i].push_back(Pi);
  a[Pi].push_back(i);
  memset(dist, -1, sizeof dist);
  dist[i] = 0;
  dfs(i);
  u[i] = u[i - 1];
  v[i] = v[i - 1];
  if (dist[v[i]] > maxDist)
  {
    u[i] = i;
    maxDist = dist[v[i]];
  }
  else if (dist[u[i]] > maxDist)
  {
    v[i] = i;
    maxDist = dist[u[i]];
  }

  if (i < FROM)
    return 0;

  if (i == FROM + POS[0] && FROM + 1 <= v[i] && v[i] < u[i])
    swap(u[i], v[i]);
  if (i == FROM + POS[0] + POS[1] - 1 && FROM + POS[0] + 1 <= v[i] && v[i] < u[i])
    swap(u[i], v[i]);

  // --------------------- phase 0 ---------------------
  if (i < FROM + POS[0])
  {
    if (i == FROM)
    {
      seqs.clear();
      seq.clear();
      gen(0, POS[0], MSG[0], -1);
      mess = toMessage(getPhase0Value(i), POS[0]);
    }

    return mess[i - FROM];
  }

  // --------------------- phase 1 ---------------------
  if (i < FROM + POS[0] + POS[1])
  {
    if (i == FROM + POS[0])
    {
      seqs.clear();
      seq.clear();
      gen(0, POS[1], MSG[1], -1);
      mess = toMessage(getPhase12Value(FROM + 1, i), POS[1]);
    }

    return mess[i - FROM - POS[0]];
  }

  // --------------------- phase 2 ---------------------
  if (i < FROM + POS[0] + POS[1] + POS[2])
  {
    if (i == FROM + POS[0] + POS[1])
    {
      int value = getPhase12Value(FROM + POS[0] + 1, i - 1);
      debug("phase 2", value);
      assert(value < 21);
      mess = {value % 5, value / 5};
    }

    return mess[i - FROM - POS[0] - POS[1]];
  }

  // --------------------- phase 3 ---------------------
  // n - 2
  if (i == n - 2)
  {
    mess = {-1};
    if (match(u[i], v[i], B, C)) mess[0] = 0; // bc
    if (u[i] == B && v[i] < D) mess[0] = 0; // b_

    if (match(u[i], v[i], C, D)) mess[0] = 1; // cd
    if (u[i] == C && v[i] < D) mess[0] = 1; // c_

    if (match(u[i], v[i], B, D)) mess[0] = 2; // bd
    if (u[i] < D && v[i] == B) mess[0] = 2; // _b

    if (u[i] == D && v[i] < D) mess[0] = 3; // d_
    if (u[i] < D && v[i] == D) mess[0] = 3; // _d

    if (u[i] < D && v[i] == C) mess[0] = 4; // _c
    if (u[i] < D && v[i] < D) mess[0] = 4; // __

    return mess[0];
  }

  // n - 1
  if (mess[0] == 0)
  {
    if (match(u[i], v[i], A, B)) return 0; // ab
    if (match(u[i], v[i], A, C)) return 1; // ac
    if (match(u[i], v[i], B, C)) return 2; // bc
    if (u[i] == A && v[i] < D) return 3; // a_
    if (u[i] == B && v[i] < D) return 4; // b_
    assert(0 && "fail s[n - 2] = 0");
  }

  if (mess[0] == 1)
  {
    if (match(u[i], v[i], A, C)) return 0; // ac
    if (match(u[i], v[i], A, D)) return 1; // ad
    if (match(u[i], v[i], C, D)) return 2; // cd
    if (u[i] == A && v[i] < D) return 3; // a_
    if (u[i] == C && v[i] < D) return 4; // c_
    assert(0 && "fail s[n - 2] = 1");
  }

  if (mess[0] == 2)
  {
    if (match(u[i], v[i], A, B)) return 0; // ab
    if (match(u[i], v[i], A, D)) return 1; // ad
    if (match(u[i], v[i], B, D)) return 2; // bd
    if (u[i] < D && v[i] == A) return 3; // _a
    if (u[i] < D && v[i] == B) return 4; // _b
    assert(0 && "failed s[n - 2] = 2");
  }

  if (mess[0] == 3)
  {
    if (match(u[i], v[i], A, D)) return 0; // ad
    if (u[i] == A && v[i] < D) return 1; // a_
    if (u[i] < D && v[i] == A) return 2; // _a
    if (u[i] == D && v[i] < D) return 3; // d_
    if (u[i] < D && v[i] == D) return 4; // _d
    assert(0 && "failed s[n - 2] = 3");
  }

  if (mess[0] == 4)
  {
    if (match(u[i], v[i], A, C)) return 0; // ac
    if (u[i] == A && v[i] < D) return 1; // a_
    if (u[i] < D && v[i] == A) return 2; // _a
    if (u[i] < D && v[i] == C) return 3; // _c
    if (u[i] < D && v[i] < D) return 4; // __
    assert(0 && "failed s[n - 2] = 4");
  }

  assert(0 && "invalid s[n - 2]");
  return 0;
}

pair<vector<int>, vector<int>> getMessage(vector<int> &s, int from, int to) // [from, to)
{
  vector<int> ids, vals;
  for (int i = from; i < to; i++)
    if (s[i])
    {
      ids.push_back(i - from);
      vals.push_back(s[i]);
    }
  return {ids, vals};
}

pair<int, int> longest_path(vector<int> s)
{
  n = size(s);

  // --------------------- phase 0 ---------------------
  seqs.clear();
  seq.clear();
  gen(0, POS[0], MSG[0], -1);
  auto [ids0, vals0] = getMessage(s, FROM, FROM + POS[0]);
  int value0 = fromMessage(ids0, vals0);
  auto [u, v] = fromPhase0Value(value0);
  debug("phase 0", value0, u, v);

  // --------------------- phase 1 ---------------------
  seqs.clear();
  seq.clear();
  gen(0, POS[1], MSG[1], -1);
  auto [ids1, vals1] = getMessage(s, FROM + POS[0], FROM + POS[0] + POS[1]);
  int value1 = fromMessage(ids1, vals1);
  tie(u, v) = fromPhase12Value(value1, FROM + 1, FROM + POS[0], u, v);
  debug("phase 1", value1, u, v);

  // --------------------- phase 2 ---------------------
  int value2 = s[FROM + POS[0] + POS[1]] + s[FROM + POS[0] + POS[1] + 1] * 5;
  tie(u, v) = fromPhase12Value(value2, FROM + POS[0] + 1, FROM + POS[0] + POS[1] - 1, u, v);
  debug("phase 2", value2, u, v);

  // --------------------- phase 3 ---------------------
  if (s[n - 2] == 0)
  {
    if (s[n - 1] == 0) return {A, B};
    if (s[n - 1] == 1) return {A, C};
    if (s[n - 1] == 2) return {B, C};
    if (s[n - 1] == 3) return {A, v};
    if (s[n - 1] == 4) return {B, v};
  }

  if (s[n - 2] == 1)
  {
    if (s[n - 1] == 0) return {A, C};
    if (s[n - 1] == 1) return {A, D};
    if (s[n - 1] == 2) return {C, D};
    if (s[n - 1] == 3) return {A, v};
    if (s[n - 1] == 4) return {C, v};
  }

  if (s[n - 2] == 2)
  {
    if (s[n - 1] == 0) return {A, B};
    if (s[n - 1] == 1) return {A, D};
    if (s[n - 1] == 2) return {B, D};
    if (s[n - 1] == 3) return {u, A};
    if (s[n - 1] == 4) return {u, B};
  }

  if (s[n - 2] == 3)
  {
    if (s[n - 1] == 0) return {A, D};
    if (s[n - 1] == 1) return {A, v};
    if (s[n - 1] == 2) return {u, A};
    if (s[n - 1] == 3) return {D, v};
    if (s[n - 1] == 4) return {u, D};
  }

  if (s[n - 2] == 4)
  {
    if (s[n - 1] == 0) return {A, C};
    if (s[n - 1] == 1) return {A, v};
    if (s[n - 1] == 2) return {u, A};
    if (s[n - 1] == 3) return {u, C};
    if (s[n - 1] == 4) return {u, v};
  }

  assert(0 && "invalid s[n - 2]");
  return {u, v};
}

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