oj.uz

Submission #636257

# Submission time Handle Problem Language Result Execution time Memory
636257 2022-08-28T16:10:29 Z null_awe Flight to the Ford (BOI22_communication) C++17
90 / 100
 2644 ms 2148 KB 
#include <bits/stdc++.h>
#include <communication.h>
using namespace std;

inline void s(int& x, int b, int v) { x -= (x & (1 << b)), x |= v << b; }

void encode(int n, int x) {
  int bits = 1;
  while ((1 << bits) <= n) ++bits;
  set<int> todo; for (int i = 0; i < bits; ++i) todo.insert(i);
  vector<pair<int, int>> same, diff;
  int a = 0, b = 1, l = -1, last = -1;
  while (todo.size() > 1) {
    int b1 = *todo.begin(), b2 = *++todo.begin();
    vector<int> res(4);
    if (b1 == last) res[0] = l;
    else res[0] = send((x >> b1) & 1);
    res[1] = send((x >> b2) & 1);
    res[2] = send((x >> b2) & 1);
    if (res[1] == res[2]) {
      a |= res[1] << b2, b |= res[1] << b2;
      todo.erase(b2);
      l = res[2], last = b2;
      continue;
    }
    res[3] = send((x >> b1) & 1);
    l = res[3], last = b1;
    if (res[0] == res[3]) {
      s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
      int taken = 0;
      for (int i = 0; i < same.size() - taken; ++i)
        if (same[i].first == b1)
          swap(same[i], same[same.size() - 1 - taken++]), --i;
      for (int i = 0; i < taken; ++i) {
        s(a, same[same.size() - 1 - i].second, (a >> b1) & 1);
        s(b, same[same.size() - 1 - i].second, (b >> b1) & 1);
      }
      same.resize(same.size() - taken);
      taken = 0;
      for (int i = 0; i < diff.size() - taken; ++i)
        if (diff[i].first == b1)
          swap(diff[i], diff[diff.size() - 1 - taken++]), --i;
      for (int i = 0; i < taken; ++i) {
        s(a, diff[diff.size() - 1 - i].second, 1 - ((a >> b1) & 1));
        s(b, diff[diff.size() - 1 - i].second, 1 - ((b >> b1) & 1));
      }
      diff.resize(diff.size() - taken);
      todo.erase(b1);
    } else {
      int pa = (res[0] == res[1]), pb = 3 - pa;
      if (pa) diff.push_back({b1, b2});
      else same.push_back({b1, b2});
      if (a & (1 << b1)) a |= (pb & 1) << b2;
      else a |= (pa & 1) << b2;
      if (b & (1 << b1)) b |= (pb & 1) << b2;
      else b |= (pa & 1) << b2;
      todo.erase(b2);
    }
  }
}

pair<int, int> decode(int n) {
  int bits = 1;
  while ((1 << bits) <= n) ++bits;
  set<int> todo; for (int i = 0; i < bits; ++i) todo.insert(i);
  vector<pair<int, int>> same, diff;
  int a = 0, b = 1, l = -1, last = -1;
  while (todo.size() > 1) {
    int b1 = *todo.begin(), b2 = *++todo.begin();
    vector<int> res(4);
    if (b1 == last) res[0] = l;
    else res[0] = receive();
    res[1] = receive();
    res[2] = receive();
    if (res[1] == res[2]) {
      a |= res[1] << b2, b |= res[1] << b2;
      todo.erase(b2);
      l = res[2], last = b2;
      continue;
    }
    res[3] = receive();
    l = res[3], last = b1;
    if (res[0] == res[3]) {
      s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
      int taken = 0;
      for (int i = 0; i < same.size() - taken; ++i)
        if (same[i].first == b1)
          swap(same[i], same[same.size() - 1 - taken++]), --i;
      for (int i = 0; i < taken; ++i) {
        s(a, same[same.size() - 1 - i].second, (a >> b1) & 1);
        s(b, same[same.size() - 1 - i].second, (b >> b1) & 1);
      }
      same.resize(same.size() - taken);
      taken = 0;
      for (int i = 0; i < diff.size() - taken; ++i)
        if (diff[i].first == b1)
          swap(diff[i], diff[diff.size() - 1 - taken++]), --i;
      for (int i = 0; i < taken; ++i) {
        s(a, diff[diff.size() - 1 - i].second, 1 - ((a >> b1) & 1));
        s(b, diff[diff.size() - 1 - i].second, 1 - ((b >> b1) & 1));
      }
      diff.resize(diff.size() - taken);
      todo.erase(b1);
    } else {
      int pa = (res[0] == res[1]), pb = 3 - pa;
      if (pa) diff.push_back({b1, b2});
      else same.push_back({b1, b2});
      if (a & (1 << b1)) a |= (pb & 1) << b2;
      else a |= (pa & 1) << b2;
      if (b & (1 << b1)) b |= (pb & 1) << b2;
      else b |= (pa & 1) << b2;
      todo.erase(b2);
    }
  }
  return {max(min(a, n), 1), max(min(b, n), 1)};
}

Compilation message

communication.cpp: In function 'void encode(int, int)':
communication.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       for (int i = 0; i < same.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for (int i = 0; i < diff.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:86:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |       for (int i = 0; i < same.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:95:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |       for (int i = 0; i < diff.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1684 KB Output is correct
2 Correct 15 ms 1772 KB Output is correct
3 Correct 17 ms 1704 KB Output is correct
4 Correct 11 ms 1684 KB Output is correct
5 Correct 12 ms 1836 KB Output is correct
6 Correct 28 ms 1756 KB Output is correct
7 Correct 45 ms 1664 KB Output is correct

Subtask #2
75.000005 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 678 ms 1680 KB Output is partially correct
2 Partially correct 357 ms 1804 KB Output is partially correct
3 Partially correct 340 ms 1716 KB Output is partially correct
4 Partially correct 849 ms 1824 KB Output is partially correct
5 Partially correct 672 ms 1732 KB Output is partially correct
6 Correct 515 ms 1756 KB Output is correct
7 Correct 1761 ms 1784 KB Output is correct
8 Correct 2644 ms 2104 KB Output is correct
9 Correct 2316 ms 2052 KB Output is correct
10 Correct 2003 ms 1996 KB Output is correct
11 Correct 2472 ms 2036 KB Output is correct
12 Correct 2340 ms 1960 KB Output is correct
13 Correct 2417 ms 2148 KB Output is correct
14 Correct 2256 ms 1884 KB Output is correct
15 Correct 1154 ms 1732 KB Output is correct
16 Correct 2562 ms 1880 KB Output is correct
17 Correct 594 ms 1932 KB Output is correct
18 Correct 690 ms 1772 KB Output is correct
19 Correct 668 ms 1832 KB Output is correct
20 Correct 815 ms 1856 KB Output is correct
21 Correct 747 ms 1880 KB Output is correct
22 Correct 776 ms 1868 KB Output is correct
23 Correct 1269 ms 1880 KB Output is correct
24 Correct 9 ms 1728 KB Output is correct
25 Correct 10 ms 1680 KB Output is correct
26 Correct 15 ms 1756 KB Output is correct
27 Correct 10 ms 1680 KB Output is correct
28 Correct 11 ms 1804 KB Output is correct
29 Correct 23 ms 1820 KB Output is correct
30 Correct 56 ms 1756 KB Output is correct