Submission #1105573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105573		Zicrus	Message (IOI24_message)	C++17	100 / 100	1287 ms	1136 KiB

message

#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 (stderr)

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
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90