oj.uz

답안 #665930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
665930 2022-11-27T14:13:11 Z MilosMilutinovic Flight to the Ford (BOI22_communication) C++17
100 / 100
 3857 ms 2112 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1688 KB Output is correct
2 Correct 9 ms 1740 KB Output is correct
3 Correct 14 ms 1780 KB Output is correct
4 Correct 11 ms 1760 KB Output is correct
5 Correct 15 ms 1684 KB Output is correct
6 Correct 26 ms 1892 KB Output is correct
7 Correct 48 ms 1740 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 725 ms 1728 KB Output is correct
2 Correct 400 ms 1724 KB Output is correct
3 Correct 484 ms 1900 KB Output is correct
4 Correct 772 ms 1724 KB Output is correct
5 Correct 702 ms 1740 KB Output is correct
6 Correct 695 ms 1688 KB Output is correct
7 Correct 2651 ms 1964 KB Output is correct
8 Correct 3499 ms 2080 KB Output is correct
9 Correct 3405 ms 2112 KB Output is correct
10 Correct 3273 ms 2084 KB Output is correct
11 Correct 3792 ms 2032 KB Output is correct
12 Correct 3411 ms 1952 KB Output is correct
13 Correct 3191 ms 2072 KB Output is correct
14 Correct 3315 ms 1944 KB Output is correct
15 Correct 1725 ms 1900 KB Output is correct
16 Correct 3857 ms 1880 KB Output is correct
17 Correct 974 ms 1876 KB Output is correct
18 Correct 999 ms 1884 KB Output is correct
19 Correct 1078 ms 1744 KB Output is correct
20 Correct 975 ms 1796 KB Output is correct
21 Correct 954 ms 1824 KB Output is correct
22 Correct 1175 ms 1996 KB Output is correct
23 Correct 1739 ms 1912 KB Output is correct
24 Correct 9 ms 1680 KB Output is correct
25 Correct 18 ms 1684 KB Output is correct
26 Correct 21 ms 1688 KB Output is correct
27 Correct 12 ms 1844 KB Output is correct
28 Correct 12 ms 1764 KB Output is correct
29 Correct 32 ms 1784 KB Output is correct
30 Correct 44 ms 1760 KB Output is correct