oj.uz

Submission #1109036

# Submission time Handle Problem Language Result Execution time Memory
1109036 2024-11-05T20:55:57 Z nicksms Message (IOI24_message) C++17
100 / 100
 2878 ms 1088 KB 
#include "message.h"
#include <bits/stdc++.h>

void send_message(std::vector<bool> M, std::vector<bool> C) {
  M.push_back(M.back());
  while (M.size() < 1025) M.push_back(!M.back());
  std::vector<std::vector<bool>> messages(16);
  std::vector<int> k(16);
  int c = 0, t = 0;
  for (int i = 0; i < 31; i++) {if (C[i]) c++; else k[t++]=c,c=0;}
  k[0] += c;
  int ind = 0;
  for (int i = 0; i < 16; i++) {
    while (k[i]--) messages[i].push_back(true);
    messages[i].push_back(false);
    while (messages[i].size() < 66) messages[i].push_back(M[ind++]);
    // std::cout << i << " " << ind << std::endl;
  }
  for (int i = 0; i < 66; i++) {
    std::vector<bool> tmp(31);
    int k = 0;
    for (int j = 0; j < 31; j++)
      if (!C[j]) tmp[j]=messages[k++][i];
    // for (int i : tmp) std::cout << i << " ";
    // std::cout << std::endl;
    send_packet(tmp);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  assert(R.size() == 66);
  std::vector<int> k(31);
  std::vector<bool> C(31,1);
  for (int i = 0; i < 66; i++)
    for (int j = 0; j < 31; j++)
      if (k[j] == i && R[i][j]) k[j]++;
  for (int j = 0; j < 31; j++) {
    int h = 0;
    int cur = j;
    while (h < 100 && (!h || cur != j)) {
      h++;
      cur = (3100 + cur - k[cur]-1) % 31;
    }
    if (h == 16) C[j]=0;
    // std::cout << j << " " << h << " " << k[j] << std::endl;
  }
  // for (int i : C) std::cout << i << " ";
  // std::cout << std::endl;
  std::vector<bool> M;
  for (int i = 0; i < 31; i++) {
    if (C[i]) continue;
    bool seen = false;
    for (int j = 0; j < 66; j++) {
      if (seen) M.push_back(R[j][i]);
      else if (!R[j][i]) seen=true;
    }
  }
  while (M[M.size()-1] != M[M.size()-2]) M.pop_back();
  M.pop_back();
  return M;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 752 KB Used 66 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2878 ms 832 KB Used 66 days
2 Correct 2684 ms 844 KB Used 66 days
3 Correct 2796 ms 1008 KB Used 66 days
4 Correct 2736 ms 920 KB Used 66 days
5 Correct 1974 ms 852 KB Used 66 days
6 Correct 1463 ms 832 KB Used 66 days
7 Correct 1707 ms 1084 KB Used 66 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 752 KB Used 66 days
2 Correct 2878 ms 832 KB Used 66 days
3 Correct 2684 ms 844 KB Used 66 days
4 Correct 2796 ms 1008 KB Used 66 days
5 Correct 2736 ms 920 KB Used 66 days
6 Correct 1974 ms 852 KB Used 66 days
7 Correct 1463 ms 832 KB Used 66 days
8 Correct 1707 ms 1084 KB Used 66 days
9 Correct 2758 ms 832 KB Used 66 days
10 Correct 2791 ms 852 KB Used 66 days
11 Correct 2834 ms 832 KB Used 66 days
12 Correct 2706 ms 852 KB Used 66 days
13 Correct 2772 ms 856 KB Used 66 days
14 Correct 1956 ms 824 KB Used 66 days
15 Correct 1489 ms 1088 KB Used 66 days
16 Correct 1907 ms 828 KB Used 66 days
17 Correct 1984 ms 1080 KB Used 66 days
18 Correct 2842 ms 1080 KB Used 66 days
19 Correct 2810 ms 852 KB Used 66 days
20 Correct 2782 ms 856 KB Used 66 days
21 Correct 2773 ms 828 KB Used 66 days
22 Correct 2718 ms 856 KB Used 66 days
23 Correct 2725 ms 864 KB Used 66 days
24 Correct 2777 ms 856 KB Used 66 days
25 Correct 2768 ms 864 KB Used 66 days
26 Correct 2819 ms 852 KB Used 66 days
27 Correct 2748 ms 1016 KB Used 66 days
28 Correct 2721 ms 928 KB Used 66 days