Submission #1307029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307029		succe_ed	Message (IOI24_message)	C++20	0 / 100	59 ms	732 KiB

message

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

using namespace std;

// Aisha's Logic
void send_message(std::vector<bool> M, std::vector<bool> C) {
    int S = M.size();
    vector<int> allies;
    for (int i = 0; i < 31; ++i) if (!C[i]) allies.push_back(i);

    // Phase 1: Identify one specific Ally index to Basma
    // We use 4 packets to find 1 out of 16 allies.
    vector<int> current_candidates = allies;
    vector<int> known_spies;
    
    for (int round = 0; round < 4; ++round) {
        vector<bool> packet(31, 0);
        // Split candidates into two groups. Group A sends 0, Group B sends 1.
        int half = current_candidates.size() / 2;
        for (int i = 0; i < half; ++i) packet[current_candidates[i]] = 0;
        for (int i = half; i < current_candidates.size(); ++i) packet[current_candidates[i]] = 1;
        
        vector<bool> tainted = send_packet(packet);
        
        // Aisha sees what Cleopatra did and narrows down the candidates
        // Based on Basma's majority rule logic
        int count0 = 0, count1 = 0;
        for (int idx : current_candidates) {
            if (tainted[idx] == 0) count0++;
            else count1++;
        }
        
        vector<int> next_candidates;
        bool chosen_bit = (count1 > count0); // Basma will pick the majority
        for (int idx : current_candidates) {
            if (tainted[idx] == (chosen_bit)) next_candidates.push_back(idx);
        }
        current_candidates = next_candidates;
    }

    // Phase 2: Use the identified known_ally (current_candidates[0]) 
    // to tell Basma where all other 15 allies are.
    int known_ally = current_candidates[0];
    
    // We need to send 30 bits of info (the C array, excluding known_ally)
    // We can send 15 bits of 'C' per packet using the 15 other allies.
    for (int p = 0; p < 2; ++p) {
        vector<bool> packet(31, 0);
        int bit_offset = p * 15;
        int ally_idx = 0;
        for (int i = 0; i < 31; ++i) {
            if (i == known_ally) continue;
            // Use allies to send the C array values
            if (!C[i]) {
                if (bit_offset < 31) {
                   // Logic to send C[idx] info
                }
            }
        }
        send_packet(packet);
    }

    // Phase 3: Send actual message M
    // With 16 indices, we can send 16 bits per packet.
    int m_ptr = 0;
    while (m_ptr < S) {
        vector<bool> packet(31, 0);
        for (int i = 0; i < 16 && m_ptr < S; ++i) {
            packet[allies[i]] = M[m_ptr++];
        }
        send_packet(packet);
    }
}

// Basma's Logic
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    vector<int> candidates(31);
    iota(candidates.begin(), candidates.end(), 0);

    // Reconstruct Phase 1: Identify the known_ally
    for (int round = 0; round < 4; ++round) {
        int c0 = 0, c1 = 0;
        for (int idx : candidates) {
            if (R[round][idx] == 0) c0++;
            else c1++;
        }
        bool majority = (c1 > c0);
        vector<int> next;
        for (int idx : candidates) if (R[round][idx] == majority) next.push_back(idx);
        candidates = next;
    }
    int known_ally = candidates[0];

    // Reconstruct Phase 2 & 3: Get C and M
    vector<bool> M;
    // ... Logic to extract based on known_ally ...
    return M;
}

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