Submission #665930

#	Time	Username	Problem	Language	Result	Execution time	Memory
665930		MilosMilutinovic	Flight to the Ford (BOI22_communication)	C++17	100 / 100	3857 ms	2112 KiB

communication

#include "communication.h"

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> merge_vec(vector<pair<int, int>> x, vector<pair<int, int>> y) {
  int sz_x = x.size();
  int sz_y = y.size();
  int i = 0, j = 0;
  vector<pair<int, int>> res;
  while (i < sz_x || j < sz_y) {
    if (j == sz_y || (i < sz_x && x[i].first < y[j].first)) {
      if (res.empty() || res.back().second != x[i].first - 1) {
        res.push_back(x[i]);
      } else {
        res.back().second = x[i].second;
      }
      i++;
    } else {
      if (res.empty() || res.back().second != y[j].first - 1) {
        res.push_back(y[j]);
      } else {
        res.back().second = y[j].second;
      }
      j++;
    }
  }
  return res;
}

struct state {
  vector<pair<int, int>> interval;
  int len;
  state(int N) {
    if (N == -1) {
      len = 0;
      interval = {};
    } else {
      len = N;
      interval = {make_pair(1, N)};
    }
  }
  void add(pair<int, int> p) {
    interval = merge_vec(interval, {p});
    len += p.second - p.first + 1;
  }
  bool in(int x) {
    for (auto& p : interval) {
      if (p.first <= x && x <= p.second) {
        return true;
      }
    }
    return false;
  }
  pair<state, state> split(int delta) {
    state L(-1);
    state R(-1);
    if (len == 0) {
      return {L, R};
    }
    for (auto& p : interval) {
      if (L.len + p.second - p.first + 1 <= (len + delta) / 2) {
        L.add(p);
      } else if (L.len >= (len + delta) / 2) {
        R.add(p);
      } else {
        L.add({p.first, p.first + (len + delta) / 2 - L.len - 1});
        assert(!L.interval.empty());
        R.add({L.interval.back().second + 1, p.second});
      }
    }
    return {L, R};
  }
  vector<int> all() {
    vector<int> v;
    for (auto& p : interval) {
      for (int i = p.first; i <= p.second; i++) {
        v.push_back(i);
      }
    }
    return v;
  }
};

state Merge(state p, state q) {
  state ret(-1);
  ret.interval = merge_vec(p.interval, q.interval);
  ret.len = p.len + q.len;
  return ret;
}

pair<int, int> solve(int N, int X) {
  state good(N);
  state bad(-1);
  while (good.len + bad.len > 3) {
    auto good_split = good.split(0);
    state good_L = good_split.first;
    state good_R = good_split.second;
    auto bad_split = bad.split(1);
    state bad_L = bad_split.first;
    state bad_R = bad_split.second;

//    cout << "good_L = ";
//    for (auto& p : good_L.interval) {
//      cout << p.first << " " << p.second << '\n';
//    }
//    cout << '\n';
//    cout << "good_R = ";
//    for (auto& p : good_R.interval) {
//      cout << p.first << " " << p.second << '\n';
//    }
//    cout << '\n';
//    cout << "bad_L = ";
//    for (auto& p : bad_L.interval) {
//      cout << p.first << " " << p.second << '\n';
//    }
//    cout << '\n';
//    cout << "bad_R = ";
//    for (auto& p : bad_R.interval) {
//      cout << p.first << " " << p.second << '\n';
//    }
//    cout << '\n';

    int f;
    if (X == -1) {
      f = receive();
    } else {
      f = send(good_L.in(X) || bad_L.in(X));
    }
    if (f == 0) {
      good = Merge(good_R, bad_R);
      bad = good_L;
    } else {
      good = Merge(good_L, bad_L);
      bad = good_R;
    }
  }
  vector<int> nums = Merge(good, bad).all();
  if (nums.size() == 3) {
    if (X != -1) {
      if (nums[0] == X) {
        send(0);
        send(0);
        send(0);
        send(0);
      }
      if (nums[1] == X) {
        send(0);
        send(1);
        send(1);
        send(0);
      }
      if (nums[2] == X) {
        send(1);
        send(1);
        send(1);
        send(1);
      }
    } else {
      vector<vector<int>> f;
      f.push_back({0, 0, 0, 0});
      f.push_back({0, 1, 1, 0});
      f.push_back({1, 1, 1, 1});
      vector<int> seq;
      seq.push_back(receive());
      seq.push_back(receive());
      seq.push_back(receive());
      seq.push_back(receive());
      vector<int> new_nums;
      for (int i = 0; i < 3; i++) {
        bool ok = true;
        for (int j = 1; j < 4; j++) {
          if (seq[j] != f[i][j] && seq[j - 1] != f[i][j - 1]) {
            ok = false;
          }
        }
        if (ok) {
          new_nums.push_back(nums[i]);
        }
      }
      swap(new_nums, nums);
    }
  }
  if (nums.size() == 1) {
    return {nums[0], nums[0]};
  }
  return {nums[0], nums[1]};
}

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

pair<int, int> decode(int N) {
  return solve(N, -1);
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85