oj.uz

Submission #635228

# Submission time Handle Problem Language Result Execution time Memory
635228 2022-08-25T17:08:51 Z null_awe Flight to the Ford (BOI22_communication) C++17
74 / 100
 3493 ms 2048 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) {
  set<int> todo; for (int i = 0; i < 30; ++i) todo.insert(i);
  vector<pair<int, int>> same, diff;
  int a = 0, b = 0; b |= 1;
  while (todo.size() > 1) {
    int b1 = *todo.begin(), b2 = *++todo.begin();
    vector<int> res(4);
    res[0] = send((x >> b1) & 1);
    res[1] = send((x >> b2) & 1);
    res[2] = send((x >> b2) & 1);
    res[3] = send((x >> b1) & 1);
    if (res[1] == res[2]) {
      a |= res[1] << b2, b |= res[1] << b2;
      todo.erase(b2);
    } else if (res[0] == res[3]) {
      s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
      int cur = b1;
      while (same.size() || diff.size()) {
        pair<int, int> l;
        if (same.size()) {
          for (int i = 0; i < same.size(); ++i) {
            if (same[i].second == cur) {
              swap(same[i], same[same.size() - 1]);
              break;
            }
          }
          l = same.back();
          if (l.second == cur) {
            s(a, l.first, (a >> cur) & 1);
            s(b, l.first, (b >> cur) & 1);
            cur = l.first;
            same.resize(same.size() - 1);
            continue;
          }
        }
        if (!diff.size()) break;
        for (int i = 0; i < diff.size(); ++i) {
          if (diff[i].second == cur) {
            swap(diff[i], diff[diff.size() - 1]);
            break;
          }
        }
        l = diff.back();
        if (l.second != cur) break;
        s(a, l.first, 1 - ((a >> cur) & 1));
        s(b, l.first, 1 - ((b >> cur) & 1));
        cur = l.first;
        diff.resize(diff.size() - 1);
      }
      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(b1);
    }
  }
}

pair<int, int> decode(int n) {
  set<int> todo; for (int i = 0; i < 30; ++i) todo.insert(i);
  vector<pair<int, int>> same, diff;
  int a = 0, b = 0; b |= 1;
  while (todo.size() > 1) {
    int b1 = *todo.begin(), b2 = *++todo.begin();
    vector<int> res(4);
    for (int i = 0; i < 4; ++i) res[i] = receive();
    if (res[1] == res[2]) {
      a |= res[1] << b2, b |= res[1] << b2;
      todo.erase(b2);
    } else if (res[0] == res[3]) {
      s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
      int cur = b1;
      while (same.size() || diff.size()) {
        pair<int, int> l;
        if (same.size()) {
          for (int i = 0; i < same.size(); ++i) {
            if (same[i].second == cur) {
              swap(same[i], same[same.size() - 1]);
              break;
            }
          }
          l = same.back();
          if (l.second == cur) {
            s(a, l.first, (a >> cur) & 1);
            s(b, l.first, (b >> cur) & 1);
            cur = l.first;
            same.resize(same.size() - 1);
            continue;
          }
        }
        if (!diff.size()) break;
        for (int i = 0; i < diff.size(); ++i) {
          if (diff[i].second == cur) {
            swap(diff[i], diff[diff.size() - 1]);
            break;
          }
        }
        l = diff.back();
        if (l.second != cur) break;
        s(a, l.first, 1 - ((a >> cur) & 1));
        s(b, l.first, 1 - ((b >> cur) & 1));
        cur = l.first;
        diff.resize(diff.size() - 1);
      }
      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(b1);
    }
  }
  return {max(min(a, n), 1), max(min(b, n), 1)};
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1728 KB Output is correct
2 Correct 163 ms 1816 KB Output is correct
3 Correct 161 ms 1672 KB Output is correct
4 Correct 94 ms 1756 KB Output is correct
5 Correct 156 ms 1816 KB Output is correct
6 Correct 349 ms 1732 KB Output is correct
7 Correct 851 ms 1664 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 805 ms 1672 KB Output is partially correct
2 Partially correct 448 ms 1680 KB Output is partially correct
3 Partially correct 531 ms 1716 KB Output is partially correct
4 Partially correct 576 ms 1732 KB Output is partially correct
5 Partially correct 787 ms 1684 KB Output is partially correct
6 Partially correct 677 ms 1672 KB Output is partially correct
7 Partially correct 2349 ms 1884 KB Output is partially correct
8 Partially correct 3427 ms 2040 KB Output is partially correct
9 Partially correct 3116 ms 1976 KB Output is partially correct
10 Partially correct 2997 ms 1892 KB Output is partially correct
11 Partially correct 3259 ms 1972 KB Output is partially correct
12 Partially correct 3050 ms 1800 KB Output is partially correct
13 Partially correct 3080 ms 2048 KB Output is partially correct
14 Partially correct 2964 ms 1820 KB Output is partially correct
15 Partially correct 1639 ms 1764 KB Output is partially correct
16 Partially correct 3493 ms 1832 KB Output is partially correct
17 Partially correct 786 ms 1736 KB Output is partially correct
18 Partially correct 881 ms 1752 KB Output is partially correct
19 Partially correct 913 ms 1724 KB Output is partially correct
20 Partially correct 839 ms 1768 KB Output is partially correct
21 Partially correct 729 ms 1752 KB Output is partially correct
22 Partially correct 948 ms 1868 KB Output is partially correct
23 Partially correct 1484 ms 1724 KB Output is partially correct
24 Correct 98 ms 1660 KB Output is correct
25 Correct 164 ms 1732 KB Output is correct
26 Correct 140 ms 1664 KB Output is correct
27 Correct 116 ms 1752 KB Output is correct
28 Correct 147 ms 1660 KB Output is correct
29 Correct 388 ms 1804 KB Output is correct
30 Correct 688 ms 1724 KB Output is correct