oj.uz

Submission #635224

# Submission time Handle Problem Language Result Execution time Memory
635224 2022-08-25T16:57:34 Z null_awe Flight to the Ford (BOI22_communication) C++17
70 / 100
 3924 ms 2156 KB 
#include <vector>
#include <set>
#include <iostream>
#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, v = 1;
  while (v < n) ++bits, v <<= 1;
  set<int> todo; for (int i = 0; i < bits; ++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) {
  int bits = 1, v = 1;
  while (v < n) ++bits, v <<= 1;
  set<int> todo; for (int i = 0; i < bits; ++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:31: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]
   31 |           for (int i = 0; i < same.size(); ++i) {
      |                           ~~^~~~~~~~~~~~~
communication.cpp:47: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]
   47 |         for (int i = 0; i < diff.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:93: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]
   93 |           for (int i = 0; i < same.size(); ++i) {
      |                           ~~^~~~~~~~~~~~~
communication.cpp:109: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]
  109 |         for (int i = 0; i < diff.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1832 KB Output is correct
2 Correct 16 ms 1756 KB Output is correct
3 Correct 26 ms 1684 KB Output is correct
4 Correct 16 ms 1756 KB Output is correct
5 Correct 20 ms 1704 KB Output is correct
6 Correct 31 ms 1760 KB Output is correct
7 Correct 64 ms 1680 KB Output is correct

Subtask #2
55.000015 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 850 ms 1684 KB Output is partially correct
2 Partially correct 267 ms 1840 KB Output is partially correct
3 Partially correct 574 ms 1752 KB Output is partially correct
4 Partially correct 853 ms 1796 KB Output is partially correct
5 Partially correct 749 ms 1768 KB Output is partially correct
6 Partially correct 653 ms 1672 KB Output is partially correct
7 Partially correct 2437 ms 1904 KB Output is partially correct
8 Partially correct 3656 ms 2056 KB Output is partially correct
9 Partially correct 3209 ms 2156 KB Output is partially correct
10 Partially correct 3168 ms 1900 KB Output is partially correct
11 Partially correct 3209 ms 2056 KB Output is partially correct
12 Partially correct 3414 ms 1976 KB Output is partially correct
13 Partially correct 3259 ms 2108 KB Output is partially correct
14 Partially correct 3455 ms 1828 KB Output is partially correct
15 Partially correct 1771 ms 1792 KB Output is partially correct
16 Partially correct 3924 ms 1740 KB Output is partially correct
17 Partially correct 903 ms 1764 KB Output is partially correct
18 Partially correct 896 ms 1792 KB Output is partially correct
19 Partially correct 973 ms 1788 KB Output is partially correct
20 Partially correct 973 ms 1736 KB Output is partially correct
21 Partially correct 893 ms 1728 KB Output is partially correct
22 Partially correct 813 ms 1796 KB Output is partially correct
23 Partially correct 1581 ms 1848 KB Output is partially correct
24 Correct 12 ms 1704 KB Output is correct
25 Correct 19 ms 1740 KB Output is correct
26 Correct 22 ms 1764 KB Output is correct
27 Correct 16 ms 1860 KB Output is correct
28 Correct 22 ms 1936 KB Output is correct
29 Correct 46 ms 1788 KB Output is correct
30 Correct 54 ms 1664 KB Output is correct