oj.uz

Submission #573919

# Submission time Handle Problem Language Result Execution time Memory
573919 2022-06-07T12:08:27 Z lumibons Flight to the Ford (BOI22_communication) C++17
75 / 100
 7566 ms 2512 KB 
#include <vector>
#include <cstdlib>
#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 = 0;
  vector<interval> c;
  state() {}
  state(ll N): s(N) {
    c.emplace_back(1, N + 1);
  }
  state(vector<vector<interval>> &cs) {
    for (vector<interval> &c : cs)
      add(c);
  }
  void add(interval it) {
    s += it.length();
    c.push_back(it);
  }
  void add(vector<interval> &c) {
    for (interval &it : c)
      add(it);
  }
  vector<vector<interval>> split(int n) {
    vector<vector<interval>> r;
    ll o = 0, rs = s;
    for (int i = 0; i < n; i++) {
      ll cs = rs / (n - i);
      rs -= cs;
      r.push_back(splitIntervals(c, o, cs));
      o += cs;
    }
    return r;
  }
  ll size() {
    return s;
  }
  vector<ll> remaining() {
    vector<ll> r;
    for (interval &it : c)
      for (ll v = it.l; v < it.r; v++)
        r.push_back(v);
    return r;
  }
};

void reduce(state &s, int ps, const vector<int> &p, int X = -1) {
  // if (rand() & 1)
  //   X != -1 ? send(0) : receive();
  int rp = 0, pc = (int) p.size();
  vector<vector<interval>> c = s.split(pc);
  int sp = 0;
  while (X != -1 && !contains(c[sp], X))
    sp++;
  for (int i = 0; i < ps; i++)
    rp |= (X != -1 ? send((p[sp] >> i) & 1) : receive()) << i;
  vector<vector<interval>> nc;
  for (int i = 0; i < pc; i++)
    if (((p[i] ^ rp) & ((p[i] ^ rp) >> 1)) == 0)
      nc.push_back(c[i]);
  s = state(nc);
}

std::pair<int, int> solve(int N, int X = -1) {
  state s(N);
  srand(42);

  for (int ps = 8; ps >= 4; ps -= 2) {
     vector<int> p;
     for (int i = 0; i < (1 << ps); i++)
       p.push_back(i);
     while (s.size() >= (int) p.size())
       reduce(s, ps, p, X);
  }
  // -> 106, ok

  // int ps = 10;
  // vector<int> p;
  // for (int i = 0; i < (1 << ps); i++)
  //   p.push_back(i);
  // while (s.size() >= (int) p.size())
  //   reduce(s, ps, p, X);
  // -> 108, ok

  while (s.size() >= 6)
    reduce(s, 5, {0, 3, 12, 17, 10, 31}, X); // -> 224, ok
    // reduce(s, 4, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, X); // -> 116, ok
    // reduce(s, 4, {1, 2, 4, 15}, X); // -> >250, ok
    // reduce(s, 4, {0, 7, 9, 15}, X); // -> >250, ok

  while (s.size() > 2)
    reduce(s, 4, {0, 6, 9, 15}, X);

  vector<ll> r = s.remaining();
  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 8 ms 1704 KB Output is correct
2 Correct 14 ms 1672 KB Output is correct
3 Correct 15 ms 1680 KB Output is correct
4 Correct 14 ms 1676 KB Output is correct
5 Correct 14 ms 1764 KB Output is correct
6 Correct 28 ms 1736 KB Output is correct
7 Correct 45 ms 1936 KB Output is correct

Subtask #2
59.99997 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1542 ms 1904 KB Output is partially correct
2 Partially correct 665 ms 1812 KB Output is partially correct
3 Partially correct 951 ms 1960 KB Output is partially correct
4 Partially correct 1564 ms 1832 KB Output is partially correct
5 Partially correct 1446 ms 1884 KB Output is partially correct
6 Partially correct 1242 ms 1848 KB Output is partially correct
7 Partially correct 5043 ms 2144 KB Output is partially correct
8 Partially correct 7566 ms 2512 KB Output is partially correct
9 Partially correct 6540 ms 2332 KB Output is partially correct
10 Partially correct 7226 ms 2404 KB Output is partially correct
11 Partially correct 7475 ms 2348 KB Output is partially correct
12 Partially correct 6744 ms 2388 KB Output is partially correct
13 Partially correct 6645 ms 2396 KB Output is partially correct
14 Partially correct 6701 ms 2504 KB Output is partially correct
15 Partially correct 3369 ms 2140 KB Output is partially correct
16 Partially correct 7126 ms 2096 KB Output is partially correct
17 Partially correct 1821 ms 2068 KB Output is partially correct
18 Partially correct 1801 ms 2108 KB Output is partially correct
19 Partially correct 1676 ms 2088 KB Output is partially correct
20 Partially correct 1828 ms 2044 KB Output is partially correct
21 Partially correct 1819 ms 2184 KB Output is partially correct
22 Partially correct 1803 ms 2040 KB Output is partially correct
23 Partially correct 2812 ms 2100 KB Output is partially correct
24 Correct 9 ms 1680 KB Output is correct
25 Correct 15 ms 1812 KB Output is correct
26 Correct 11 ms 1680 KB Output is correct
27 Correct 8 ms 1724 KB Output is correct
28 Correct 13 ms 1764 KB Output is correct
29 Correct 26 ms 1892 KB Output is correct
30 Correct 47 ms 1684 KB Output is correct