oj.uz

답안 #636256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636256 2022-08-28T15:54:02 Z null_awe Flight to the Ford (BOI22_communication) C++17
90 / 100
 2778 ms 2092 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 = 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) {
  set<int> todo; for (int i = 0; i < 30; ++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:29: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]
   29 |       for (int i = 0; i < same.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:38: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]
   38 |       for (int i = 0; i < diff.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:82: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]
   82 |       for (int i = 0; i < same.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:91: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]
   91 |       for (int i = 0; i < diff.size() - taken; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 1680 KB Output is correct
2 Correct 141 ms 1848 KB Output is correct
3 Correct 175 ms 1780 KB Output is correct
4 Correct 69 ms 1704 KB Output is correct
5 Correct 118 ms 1720 KB Output is correct
6 Correct 276 ms 1808 KB Output is correct
7 Correct 521 ms 1672 KB Output is correct

Subtask #2
75.000005 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 821 ms 1664 KB Output is partially correct
2 Partially correct 378 ms 1784 KB Output is partially correct
3 Partially correct 468 ms 1872 KB Output is partially correct
4 Partially correct 613 ms 1776 KB Output is partially correct
5 Partially correct 632 ms 1848 KB Output is partially correct
6 Correct 425 ms 1740 KB Output is correct
7 Correct 2055 ms 1764 KB Output is correct
8 Correct 2778 ms 1944 KB Output is correct
9 Correct 2437 ms 2080 KB Output is correct
10 Correct 2548 ms 1968 KB Output is correct
11 Correct 2369 ms 2060 KB Output is correct
12 Correct 2521 ms 1876 KB Output is correct
13 Correct 2377 ms 2092 KB Output is correct
14 Correct 2441 ms 1920 KB Output is correct
15 Correct 1257 ms 1876 KB Output is correct
16 Correct 2699 ms 1748 KB Output is correct
17 Correct 750 ms 1724 KB Output is correct
18 Correct 628 ms 2024 KB Output is correct
19 Correct 573 ms 1788 KB Output is correct
20 Correct 692 ms 1740 KB Output is correct
21 Correct 723 ms 1880 KB Output is correct
22 Correct 715 ms 1880 KB Output is correct
23 Correct 1041 ms 1844 KB Output is correct
24 Correct 100 ms 1732 KB Output is correct
25 Correct 107 ms 1876 KB Output is correct
26 Correct 159 ms 1732 KB Output is correct
27 Correct 79 ms 1700 KB Output is correct
28 Correct 99 ms 1880 KB Output is correct
29 Correct 325 ms 1800 KB Output is correct
30 Correct 467 ms 1700 KB Output is correct