Submission #1206844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206844		Andrey	메시지 (IOI24_message)	C++20	90.25 / 100	408 ms	864 KiB

message

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

void send_message(std::vector<bool> m, std::vector<bool> c) {
    m.push_back(1);
    while(m.size() < 1025) {
        m.push_back(0);
    }
    int sm = INT_MAX,p = -1,z = 0;
    int l = 0,r = 30,w = 16;
    for(int i = 0; i < 4; i++) {
        vector<bool> wut(31);
        vector<int> wow(31);
        int mid = (l+r)/2;
        int br = 0;
        for(int j = l; j < mid; j++) {
            if(c[j] == 0) {
                br++;
            }
        }
        for(int j = mid+1; j <= r; j++) {
            if(c[j] == 0) {
                br--;
            }
        }
        int u = 0;
        bool t;
        if(br >= 0) {
            t = 0;
        }
        else {
            t = 1;
        }
        for(int j = l; j <= r; j++) {
            if(c[j] == 0 && u < w) {
                wut[j] = t;
                wow[j] = -1;
                u++;
            }
        }
        for(int j = 0; j < 31; j++) {
            if(c[j] == 0 && wow[j] == 0) {
                wut[j] = m[z];
                z++;
            }
        }
        send_packet(wut);
        w/=2;
        if(br >= 0) {
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    p = l;
    int y = 1;
    while(y < 31) {
        int x = p+y,x1 = p;
        vector<bool> wut(31);
        for(int i = p; i < p+min(31,y); i++) {
            if(c[i%31] == 0) {
                y++;
                x1 = i+1;
                wut[i%31] = c[x%31];
                x++;
            }
            if(y == 31) {
                break;
            }
        }
        for(int i = x1; i < p+31; i++) {
            if(c[i%31] == 0) {
                wut[i%31] = m[z];
                z++;
            }
        }
        send_packet(wut);
    }
    while(z < 1025) {
        vector<bool> wut(31);
        for(int i = 0; i < 31; i++) {
            if(z < 1025 && c[i] == 0) {
                wut[i] = m[z];
                z++;
            }
        }
        send_packet(wut);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> r) {
    int l = 0,zr = 30;
    for(int i = 0; i < 4; i++) {
        int br = 0;
        int mid = (l+zr)/2;
        for(int j = l; j <= zr; j++) {
            if(r[i][j] == 0) {
                br++;
            }
            else {
                br--;
            }
        }
        if(br >= 0) {
            zr = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    int p = l;
    int y = 1;
    int x = 4;
    vector<bool> wow(1,false);
    vector<vector<int>> banana(0);
    while(wow.size() < 31) {
        vector<int> apple(0);
        for(int i = 0; i < 31; i++) {
            apple.push_back(r[x][(i+p)%31]);
        }
        for(int j = 0; j < min((int)wow.size(),31); j++) {
            apple[j] = -1;
            if(wow[j] == false) {
                wow.push_back(r[x][(j+p)%31]);
            }
            if(wow.size() == 31) {
                break;
            }
        }
        banana.push_back(apple);
        x++;
    }
    vector<bool> c(31);
    for(int i = 0; i < 31; i++) {
        c[i] = wow[(i-p+31)%31];
    }
    vector<bool> m(0);
    l = 0;
    zr = 30;
    int w = 16;
    for(int i = 0; i < 4; i++) {
        int br = 0;
        int mid = (l+zr)/2;
        bool t;
        int u = 0;
        vector<int> wut(31);
        for(int j = l; j <= zr; j++) {
            if(c[j] == 0 && u < w) {
                u++;
                wut[j] = -1;
            }
        }
        for(int j = 0; j < 31; j++) {
            if(c[j] == 0 && wut[j] == 0) {
                m.push_back(r[i][j]);
            }
        }
        if(p < mid) {
            zr = mid-1;
        }
        else {
            l = mid+1;
        }
        w/=2;
    }
    for(vector<int> apple: banana) {
        for(int i = 0; i < 31; i++) {
            if(apple[i] != -1 && wow[i] == 0) {
                m.push_back(apple[i]);
            }
        }
    }
    for(int i = x; i < r.size(); i++) {
        for(int j = 0; j < 31; j++) {
            if(c[j] == 0 && m.size() <= 1025) {
                m.push_back(r[i][j]);
            }
        }
    }
    while(m[m.size()-1] == 0) {
        m.pop_back();
    }
    m.pop_back();
    return m;
}

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