제출 #1198665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198665		Szil	메시지 (IOI24_message)	C++20	100 / 100	413 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void send_message(vector<bool> M, vector<bool> C) {
    {
        int S = M.size();
        vector<bool> message;
        for (int i = 0; i < 1024-S; i++) message.emplace_back(0);
        message.emplace_back(1);
        for (bool x : M) message.emplace_back(x);
        M = message;
    }
    assert(M.size() == 1025);
    vector<int> diff(31);
    {
        vector<bool> v;
        for (bool x : C) v.emplace_back(x);
        for (bool x : C) v.emplace_back(x);

        for (int i = 0; i < 31; i++) {
            if (C[i] == 1) continue;
            for (int j = i+1; j < 62; j++) {
                if (v[j] == 0) {
                    diff[i] = j-i;
                    break;
                }
            }
        }
    }

    int ptr = 0;
    int cnt = 0;

    for (int i = 0; i < 16; i++) {
        vector<bool> v(31);
        for (int j = 0; j < 31; j++) {
            if (C[j] == 1) continue;

            if (diff[j] - 1 == i) {
                v[j] = 1;
            } else if (diff[j] - 1 < i) {
                if (ptr < M.size()) {
                    v[j] = M[ptr++];
                    cnt++;
                }
            }
        }
        send_packet(v);
    }

    while (ptr < M.size()) {
        vector<bool> v;
        for (int j = 0; j < 31; j++) {
            if (C[j] == 0 && ptr < M.size()) {
                v.emplace_back(M[ptr++]);
            } else {
                v.emplace_back(0);
            }
        }
        send_packet(v);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    vector<bool> M, C(31, 1);
    vector<int> diff(31), nxt(31);
    for (int j = 0; j < 31; j++) {
        for (int i = 0; i < 16; i++) {
            if (R[i][j]) {
                diff[j] = i+1;
                break;
            }
        }
    }
    for (int j = 0; j < 31; j++) nxt[j] = max(0, (j + diff[j]) % 31);

    for (int i = 0; i < 31; i++) {
        vector<bool> vis(31);
        int u = i;
        vector<int> v;
        while (1) {
            if (u >= 31 || vis[u]) break;
            vis[u] = 1;
            v.emplace_back(u);
            u = nxt[u];
        }
        if (v.size() == 16) {
            for (int j : v) C[j] = 0;
            break;
        }
    }

    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 31; j++) {
            if (C[j] == 1) continue;

            if (diff[j] - 1 < i) {
                cnt++;
                M.emplace_back(R[i][j]);
            }
        }
    }
    
    for (int i = 16; i < R.size(); i++) {
        vector<bool> p = R[i];
        for (int j = 0; j < 31; j++) {
            if (C[j] == 0) {
                M.emplace_back(p[j]);
            }
        }
    }

    vector<bool> ans;
    bool ok = false;
    for (bool x : M) {
        if (ok) {
            ans.emplace_back(x);
        } else {
            if (x) ok = 1;
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90