Submission #1269339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269339		vincentbucourt1	Message (IOI24_message)	C++20	100 / 100	406 ms	824 KiB

message

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

void send_message(std::vector<bool> message, std::vector<bool> badBit) {
    message.push_back(1);
    vector<vector<bool>> send(66, vector<bool>(31));
    
    int finalGoodBit = 0;
    for (int iBit = 0; iBit < 31; iBit++) {
        if (!badBit[iBit]) {
            finalGoodBit = iBit;
        }
    }
    vector<int> lenDown(31, 0);
    bool firstGoodBit = true;
    int prevGoodBit = 0;
    for (int iBit = 0; iBit < 31; iBit++) {
        if (!badBit[iBit]) {
            if (firstGoodBit) {
                lenDown[iBit] = 31 - finalGoodBit + iBit;
                firstGoodBit = false;
            }
            else {
                lenDown[iBit] = iBit - prevGoodBit;
            }
            send[lenDown[iBit] - 1][iBit] = 1;
            prevGoodBit = iBit;
        }
    }

    int iMessage = 0;
    for (int iPacket = 0; iPacket < 66; iPacket++) {
        for (int iBit = 0; iBit < 31; iBit++) {
            if (!badBit[iBit] && iPacket >= lenDown[iBit] && iMessage < (int)message.size()) {
                send[iPacket][iBit] = message[iMessage];
                iMessage++;
            }
        }
    }

    for (int iPacket = 0; iPacket < 66; iPacket++) {
        send_packet(send[iPacket]);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> receive) {
    vector<int> jumpLen(31, 0);
    for (int iBit = 0; iBit < 31; iBit++) {
        int iPacket = 0;
        while (iPacket < 66 && !receive[iPacket][iBit]) {
            iPacket++;
        }
        jumpLen[iBit] = iPacket+1;
    }

    vector<bool> badBit(31, 1);
    for (int iBit = 0; iBit < 31; iBit++) {
        vector<bool> visitedBit(31, 0);
        int numVisitedBits = 0;
        int currBit = iBit;
        for (int iLen = 0; iLen < 16; iLen++) {
            assert(0 <= currBit && currBit < 31);
            if (!visitedBit[currBit]) {
                numVisitedBits++;
            }
            visitedBit[currBit] = true;
            currBit = (currBit - jumpLen[currBit] + 31*1000) % 31;
        }
        if (numVisitedBits == 16 && currBit == iBit) {
            currBit = iBit;
            for (int iLen = 0; iLen < 16; iLen++) {
                badBit[currBit] = 0;
                currBit = (currBit - jumpLen[currBit] + 31) % 31;
            }
            break;
        }
    }

    int messageLast1 = 0;
    vector<bool> message;
    for (int iPacket = 0; iPacket < 66; iPacket++) {
        for (int iBit = 0; iBit < 31; iBit++) {
            if (!badBit[iBit] && iPacket >= jumpLen[iBit]) {
                message.push_back(receive[iPacket][iBit]);
                if (receive[iPacket][iBit]) {
                    messageLast1 = (int)message.size();
                }
            }
        }
    }
    message.resize(messageLast1 - 1);
    return message;
}

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