oj.uz

Submission #1105573

# Submission time Handle Problem Language Result Execution time Memory
1105573 2024-10-26T18:52:28 Z Zicrus Message (IOI24_message) C++17
100 / 100
 1287 ms 1136 KB 
#include <bits/stdc++.h>
#include "message.h"
using namespace std;

typedef long long ll;

void send_message(vector<bool> M, vector<bool> C) {
    vector<ll> ids;
    vector<vector<ll>> cBits(16);
    for (int i = 0; i < 31; i++) {
        if (C[i] == 0) ids.push_back(i);
    }
    for (int i = 0; i < 16; i++) {
        while (cBits[i].empty() || cBits[i].back() == 0) {
            cBits[i].push_back(!C[(ids[i] + cBits[i].size() + 1) % 31]);
        }
    }
    ll k = 0;
    M.push_back(1);
    while (M.size() < 1025) M.push_back(0);
    for (int i = 0; i < 16; i++) {
        while (cBits[i].size() < 66) cBits[i].push_back(M[k++]);
    }

    vector<bool> a(31);
    for (int p = 0; p < 66; p++) {
        for (int i = 0; i < 16; i++) {
            a[ids[i]] = cBits[i][p];
        }
        send_packet(a);
    }
}

map<ll, ll> bgn;

set<ll> isFirst(vector<vector<bool>> R, ll first) {
    bgn.clear();
    ll cur = first;
    set<ll> vst;
    for (int i = 0; i < 16; i++) {
        ll nw = cur+1;
        while (nw < 100 && nw-cur-1 < R.size() && R[nw-cur-1][cur % 31] == 0) nw++;
        if (vst.count(nw%31))
            return {};
        bgn[cur] = nw-cur;
        vst.insert(nw%31);
        cur = nw;
    }
    return cur == first + 31 ? vst : set<ll>();
}

vector<bool> receive_message(vector<vector<bool>> R) {
    ll first = 0;
    while (isFirst(R, first).empty()) first++;
    set<ll> ids = isFirst(R, first);

    vector<bool> res;
    for (auto &e : ids) {
        ll p = bgn[e];
        while (p < 66) res.push_back(R[p++][e]);
    }

    while (res.back() == 0) res.pop_back();
    res.pop_back();

    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

Compilation message

message.cpp: In function 'std::set<long long int> isFirst(std::vector<std::vector<bool> >, ll)':
message.cpp:42:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (nw < 100 && nw-cur-1 < R.size() && R[nw-cur-1][cur % 31] == 0) nw++;
      |                            ~~~~~~~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 836 KB Used 66 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 1108 KB Used 66 days
2 Correct 1229 ms 856 KB Used 66 days
3 Correct 1248 ms 1116 KB Used 66 days
4 Correct 1232 ms 888 KB Used 66 days
5 Correct 905 ms 860 KB Used 66 days
6 Correct 684 ms 860 KB Used 66 days
7 Correct 799 ms 888 KB Used 66 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 836 KB Used 66 days
2 Correct 1287 ms 1108 KB Used 66 days
3 Correct 1229 ms 856 KB Used 66 days
4 Correct 1248 ms 1116 KB Used 66 days
5 Correct 1232 ms 888 KB Used 66 days
6 Correct 905 ms 860 KB Used 66 days
7 Correct 684 ms 860 KB Used 66 days
8 Correct 799 ms 888 KB Used 66 days
9 Correct 1232 ms 864 KB Used 66 days
10 Correct 1237 ms 892 KB Used 66 days
11 Correct 1251 ms 1116 KB Used 66 days
12 Correct 1268 ms 856 KB Used 66 days
13 Correct 1260 ms 888 KB Used 66 days
14 Correct 939 ms 856 KB Used 66 days
15 Correct 682 ms 860 KB Used 66 days
16 Correct 888 ms 856 KB Used 66 days
17 Correct 900 ms 860 KB Used 66 days
18 Correct 1228 ms 1112 KB Used 66 days
19 Correct 1258 ms 888 KB Used 66 days
20 Correct 1267 ms 884 KB Used 66 days
21 Correct 1242 ms 964 KB Used 66 days
22 Correct 1260 ms 884 KB Used 66 days
23 Correct 1211 ms 884 KB Used 66 days
24 Correct 1227 ms 896 KB Used 66 days
25 Correct 1243 ms 856 KB Used 66 days
26 Correct 1271 ms 860 KB Used 66 days
27 Correct 1267 ms 1136 KB Used 66 days
28 Correct 1242 ms 888 KB Used 66 days