Submission #1313885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313885		1ota	Message (IOI24_message)	C++20	0 / 100	364 ms	796 KiB

message

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

// #define int long long
#define entire(x) (x).begin(), (x).end()

// vector<vector<bool>> hint;
// void send_packet (vector<bool> a) {
//     hint.push_back(a);
// }

int m = 31, n = 66, len = 1025;

void send_message(vector<bool> mess, vector<bool> cleo){
    reverse(entire(mess)); mess.push_back(true);
    while ((int) mess.size() < len) mess.push_back(false);
    reverse(entire(mess)); for (int i = 0; i < m; i++) cleo[i] = !cleo[i];

    vector<vector<bool>> a(n, vector<bool>(m, false)), vis(n, vector<bool>(m, false));
    vector<int> next(m, 0);

    int last = 0;
    for (; !cleo[last]; last++); last += m;

    for (int bit = m-1; bit > -1; bit--) if (cleo[bit]) {
        next[bit] = last - bit; last = bit;
    }

    for (int bit = 0; bit < m; bit++){
        if (cleo[bit]) {
            a[next[bit] - 1][bit] = true;
            for (int i = 0; i < next[bit]; i++) vis[i][bit] = true;
        } else for (int i = 0; i < n; i++) vis[i][bit] = true;
    }
    

    int idx = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
        if (!vis[i][j]) a[i][j] = mess[idx++];
    }

    for (int i = 0; i < n; i++) send_packet(a[i]);
}

vector<bool> receive_message (vector<vector<bool>> a){
    vector<int> f(m, 0), next(m, 0), id(m, -1);
    for (int bit = 0; bit < m; bit++){
        int i = 0; for (; i < n and !a[i][bit]; i++);
        f[bit] = (i + 1 + bit) % m; next[bit] = i + 1;
    }

    
    int cycle = 0;
    vector<bool> visited(m, false);
    auto dfs = [&](auto&& self, int s) -> int{
        if (visited[s]) return (id[s] == -1) ? s : -1;
        else visited[s] = true;
        
        int head = self(self, f[s]);
        if (head != -1) id[s] = cycle;
        
        cycle += (head == s);
        return (head == s) ? -1 : head;
    }; for (int bit = 0; bit < m; bit++) dfs(dfs, bit);
    
    vector<int> cnt(cycle + 1, 0);
    for (int i : id) if (i != -1) cnt[i]++;
    
    int good = max_element(entire(cnt)) - cnt.begin();
    
    vector<bool> cleo(m, false);
    for (int bit = 0; bit < m; bit++) cleo[bit] = id[bit] == good;
    
    for (auto bit : cleo) cout << bit;
    cout << endl;

    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int bit = 0; bit < m; bit++){
        if (cleo[bit]){
            for (int i = 0; i < next[bit]; i++) vis[i][bit] = true;
        } else for (int i = 0; i < n; i++) vis[i][bit] = true;
    }

    vector<bool> safe, ans;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
        if (!vis[i][j]) safe.push_back(a[i][j]);
    }

    int fset = 0; for (; !safe[fset]; fset++);
    for (int i = fset + 1; i < (int) safe.size(); i++) ans.push_back(safe[i]);

    return ans;
}

// int32_t main(){
//     string cleo, message; cin >> cleo >> message;
//     int nm = (int) message.size();
//     vector<bool> c(31), m(nm);
//     for (int i = 0; i < 31; i++) c[i] = cleo[i] == '1';
//     for (int i = 0; i < nm; i++) m[i] = message[i] == '1';

//     cout << "Cleo Hoe : ";
//     for (auto bit : c) cout << bit << " ";
//     cout << endl << "Message : ";
//     for (auto bit : m) cout << bit << " ";
//     cout << endl << "[END]" << endl;

//     send_message(m, c); 

//     cout << endl;
//     vector<bool> found = receive_message(hint);
//     for (auto bit : found) cout << bit << " ";
//     cout << endl;
    
//     return 0;
// }

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