oj.uz

Submission #572571

# Submission time Handle Problem Language Result Execution time Memory
572571 2022-06-04T17:19:23 Z model_code Flight to the Ford (BOI22_communication) C++17
100 / 100
 4149 ms 2184 KB 
#include <vector>
#include "communication.h"

typedef long long ll;

using namespace std;

struct interval {
  ll l, r;
  interval(ll l, ll r) : l(l), r(r) {}
  bool contains(ll x) {
    return l <= x && x < r;
  }
  ll length() {
    return r - l;
  }
  interval shrink(ll o, ll s) {
    return interval(min(r, l + o), min(r, l + o + s));
  }
};

vector<interval> splitIntervals(vector<interval> c, ll o, ll s) {
  vector<interval> r;
  for (interval &it : c) {
    if (s > 0 && it.length() - o > 0)
      r.push_back(it.shrink(o, s));
    s -= max(0LL, min(s, it.length() - o));
    o -= min(o, it.length());
  }
  return r;
}

bool contains(vector<interval> c, ll x) {
  for (interval &it : c)
    if (it.contains(x))
      return true;
  return false;
}

struct state {
  ll s[2] = {0, 0};
  vector<vector<interval>> c;
  state(ll N): c(2) {
    s[1] = N;
    c[1].emplace_back(1, N + 1);
  }
  state(vector<vector<vector<interval>>> &cs): c(2) {
    for (int g = 0; g < 2; g++)
      for (vector<interval> &c : cs[g])
        add(g, c);
  }
  void add(int g, interval it) {
    s[g] += it.length();
    c[g].push_back(it);
  }
  void add(int g, vector<interval> &c) {
    for (interval &it : c)
      add(g, it);
  }
  vector<vector<vector<interval>>> split() {
    vector<vector<vector<interval>>> r(2);
    for (int g = 0; g < 2; g++) {
      int s1 = (s[g] + g) / 2, s2 = s[g] - s1;
      r[g].push_back(splitIntervals(c[g], 0, s1));
      r[g].push_back(splitIntervals(c[g], s1, s2));
    }
    return r;
  }
  ll size() {
    return s[0] + s[1];
  }
  vector<ll> remaining() {
    vector<ll> r;
    for (int g = 0; g < 2; g++)
      for (interval &it : c[g])
        for (ll v = it.l; v < it.r; v++)
          r.push_back(v);
    return r;
  }
};

std::pair<int, int> solve(int N, int X = -1) {
  state s(N);
  while (s.size() > 3) {
    vector<vector<vector<interval>>> c = s.split();
    int b = X != -1 ? send(contains(c[0][0], X) || contains(c[1][0], X)) : receive();
    c[0].erase(c[0].begin() + b);
    swap(c[0][0], c[1][b]);
    s = state(c);
  }
  vector<ll> r = s.remaining();
  if ((int) r.size() == 3) {
    int b1 = 1, b2;
    for (int i = 0; i < 2 && b1; i++)
      b1 = X != -1 ? send(r[0] == X || r[1] == X) : receive();
    if (!b1)
      b2 = X != -1 ? send(r[0] == X) : receive();
    r.erase(r.begin() + (b1 ? 2 : (b2 ? 1 : 0)));
  }
  return {r[0], r.back()};
}

void encode(int N, int X) {
  solve(N, X);
}

std::pair<int, int> decode(int N) {
  return solve(N);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1764 KB Output is correct
2 Correct 9 ms 1660 KB Output is correct
3 Correct 15 ms 1876 KB Output is correct
4 Correct 12 ms 1812 KB Output is correct
5 Correct 12 ms 1724 KB Output is correct
6 Correct 21 ms 1716 KB Output is correct
7 Correct 33 ms 1676 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 1776 KB Output is correct
2 Correct 423 ms 1820 KB Output is correct
3 Correct 433 ms 1772 KB Output is correct
4 Correct 879 ms 1816 KB Output is correct
5 Correct 831 ms 1808 KB Output is correct
6 Correct 598 ms 1724 KB Output is correct
7 Correct 2308 ms 1924 KB Output is correct
8 Correct 4149 ms 2184 KB Output is correct
9 Correct 3404 ms 2052 KB Output is correct
10 Correct 3530 ms 2176 KB Output is correct
11 Correct 3347 ms 2056 KB Output is correct
12 Correct 3663 ms 1948 KB Output is correct
13 Correct 3585 ms 1940 KB Output is correct
14 Correct 3354 ms 1960 KB Output is correct
15 Correct 1914 ms 1816 KB Output is correct
16 Correct 3997 ms 1968 KB Output is correct
17 Correct 956 ms 1868 KB Output is correct
18 Correct 994 ms 2028 KB Output is correct
19 Correct 925 ms 1976 KB Output is correct
20 Correct 1002 ms 1884 KB Output is correct
21 Correct 1011 ms 1860 KB Output is correct
22 Correct 974 ms 1924 KB Output is correct
23 Correct 1605 ms 1944 KB Output is correct
24 Correct 7 ms 1804 KB Output is correct
25 Correct 8 ms 1756 KB Output is correct
26 Correct 11 ms 1704 KB Output is correct
27 Correct 9 ms 2044 KB Output is correct
28 Correct 13 ms 1852 KB Output is correct
29 Correct 24 ms 1764 KB Output is correct
30 Correct 32 ms 1828 KB Output is correct