Submission #1317169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317169		spetr	Message (IOI24_message)	C++20	0 / 100	362 ms	796 KiB

message

#include <bits/stdc++.h>
#include "message.h"
using namespace std;

#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

void send_message(std::vector<bool> M, std::vector<bool> C){
    reverse(M.begin(), M.end());
    M.push_back(1);
    while (M.size() < 1025){
        M.push_back(0);
    }
    reverse(M.begin(), M.end());
    vector<vector<bool>> packets(66, vector<bool> (31, 0));

    vl depth(31, 0);
    for (ll i = 0; i < 31; i++){
        ll j = 1;
        if (!C[i]){ // Změna: Zapisujeme jen do bezpečných bitů
            while (C[(i+j)%31] == true){ // Změna: Hledáme další bezpečný (přeskakujeme true)
                j++;
            }
            packets[j-1][i] = 1;
            depth[i] = j;
        }
    }
    ll p = 0;
    for (ll i = 0; i < 31; i++){
        if (!C[i]){ // Změna: Zapisujeme jen do bezpečných bitů
            for (ll j = depth[i]; j < 66; j++){
                if (p < M.size()) { // Kontrola mezí
                    packets[j][i] = M[p];
                    p++;
                }
            }
        }
    }

    for (ll i = 0; i < 66; i++){
        send_packet(packets[i]);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
    vl pointer(31, -1);
    vl depth(31, 0);
    for (ll i = 0; i < 31; i++){
        for (ll j = 0; j < 66; j++){
            if (R[j][i]){
                if (pointer[i] == -1){
                    pointer[i] = (i+j+1)%31;
                    depth[i] = j+1;
                }
            }
        }
    }

    // Fallback pro poškozené bity, aby se algoritmus nezasekl
    for (ll i = 0; i < 31; i++){if (pointer[i] == -1) pointer[i] = (i+1)%31;}

    set<ll> c;
    for (ll i = 0; i < 31; i++){
        c.clear();
        ll pos = i;
        // Hledáme cyklus bezpečných bitů (délka >= 16)
        for (ll j = 0; j < 32; j++){ // Zvýšen limit pro jistotu
            c.insert(pos);
            pos = pointer[pos];
        }
        if (pos == pointer[pos] || c.size() >= 16){ // Heuristika pro nalezení cyklu
             // Pokud jsme našli dostatečně velkou množinu, která se točí v kruhu
             if(c.size() >= 16) break;
        }
    }
    
    // Pokud cyklus selhal (nemělo by nastat u správného řešení), fallback
    if (c.size() < 16) {
        c.clear();
        for(int i=0; i<16; ++i) c.insert(i); 
    }

    vector<bool> m;
    for (auto x: c){
        for (ll i = depth[x]; i < 66; i++){
            m.push_back(R[i][x]);
        }
    }
    
    vector<bool> M;
    ll p = 0;
    while (p < m.size() && m[p] == 0){
        p++;
    }
    p++;
    // Změna: Čteme dokud nemáme 1025 bitů nebo nedojdou data
    for (ll i = p; M.size() < 1025 && i < m.size(); i++){
        M.push_back(m[i]);
    }
    // Doplnění nulami, pokud je zpráva kratší (safety net)
    while(M.size() < 1025) M.push_back(0);
    
    return M;
}

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