oj.uz

Submission #1105028

# Submission time Handle Problem Language Result Execution time Memory
1105028 2024-10-25T07:57:48 Z flashmt Message (IOI24_message) C++17
83.3056 / 100
 1317 ms 1092 KB 
// 70 queries

#include "message.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int BIT = 31;
const int GOOD = 16;
const int FIRST = 4;
const int SECOND = 37;
const int BOUND = 400;

void send_message(std::vector<bool> m, std::vector<bool> c) {
  for (int i = 0; i < BIT; i++)
    c[i] = !c[i];

  int start = 0;
  while (!c[start])
    start++;

  vector<int> good;
  for (int i = 0; i < BIT; i++)
    if (c[(start + i) % BIT])
      good.push_back((start + i) % BIT);

  for (int i = 0; i < FIRST; i++)
    send_packet(vector<bool>(BIT, start >> i & 1));

  bool lastBit = m.back();
  int len = size(m);
  reverse(begin(m), end(m));
  auto pop = [&]()
  {
    if (empty(m))
      return !lastBit;
    bool res = m.back();
    m.pop_back();
    return res;
  };

  for (int i = 1; i < BIT - 1; i++)
  {
    vector<bool> packet(BIT);
    packet[start] = c[(start + i) % BIT];
    for (int j = 1; j < GOOD; j++)
      packet[good[j]] = pop();
    send_packet(packet);
  }

  if (len > BOUND)
    for (int i = 0; i < SECOND; i++)
    {
      vector<bool> packet(BIT);
      for (int j : good)
        packet[j] = pop();
      send_packet(packet);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> a) {
  int start = 0;
  for (int i = 0; i < FIRST; i++)
  {
    int sum = 0;
    for (auto x : a[i])
      if (x) sum++;
      else sum--;
    if (sum > 0)
      start |= 1 << i;
  }

  vector<int> good = {start};
  for (int i = 1; i < BIT - 1; i++)
    if (a[FIRST + i - 1][start])
      good.push_back((start + i) % BIT);

  if (size(good) < GOOD)
    good.push_back((start + BIT - 1) % BIT);

  vector<bool> ans;
  for (int i = 0; i < BIT - 2; i++)
    for (int j = 1; j < GOOD; j++)
      ans.push_back(a[FIRST + i][good[j]]);

  for (int i = FIRST + BIT - 2; i < size(a); i++)
    for (int j : good)
      ans.push_back(a[i][j]);

  int lastBit = ans.back();
  while (ans.back() == lastBit)
    ans.pop_back();
  return ans;
}

Compilation message

message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:89:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = FIRST + BIT - 2; i < size(a); i++)
      |                                 ~~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 33 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 844 KB Used 33 days
2 Correct 584 ms 836 KB Used 33 days
3 Correct 570 ms 836 KB Used 33 days
4 Correct 578 ms 840 KB Used 33 days
5 Correct 408 ms 840 KB Used 33 days
6 Correct 332 ms 832 KB Used 33 days
7 Correct 372 ms 824 KB Used 33 days

Subtask #2
73.3055625 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 33 days
2 Correct 607 ms 844 KB Used 33 days
3 Correct 584 ms 836 KB Used 33 days
4 Correct 570 ms 836 KB Used 33 days
5 Correct 578 ms 840 KB Used 33 days
6 Correct 408 ms 840 KB Used 33 days
7 Correct 332 ms 832 KB Used 33 days
8 Correct 372 ms 824 KB Used 33 days
9 Partially correct 1317 ms 1084 KB Used 70 days
10 Partially correct 1045 ms 1084 KB Used 70 days
11 Partially correct 1295 ms 832 KB Used 70 days
12 Partially correct 1241 ms 848 KB Used 70 days
13 Partially correct 1258 ms 856 KB Used 70 days
14 Partially correct 926 ms 1092 KB Used 70 days
15 Partially correct 666 ms 1084 KB Used 70 days
16 Partially correct 885 ms 824 KB Used 70 days
17 Partially correct 882 ms 832 KB Used 70 days
18 Correct 582 ms 852 KB Used 33 days
19 Correct 603 ms 824 KB Used 33 days
20 Correct 617 ms 848 KB Used 33 days
21 Correct 618 ms 832 KB Used 33 days
22 Partially correct 1301 ms 852 KB Used 70 days
23 Partially correct 1286 ms 836 KB Used 70 days
24 Partially correct 1225 ms 852 KB Used 70 days
25 Partially correct 1258 ms 848 KB Used 70 days
26 Partially correct 1293 ms 1080 KB Used 70 days
27 Partially correct 1282 ms 832 KB Used 70 days
28 Partially correct 1230 ms 1088 KB Used 70 days