Submission #1206578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206578		Andrey	Message (IOI24_message)	C++20	81.45 / 100	412 ms	856 KiB

message

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

int calc(vector<bool> c, int p) {
    if(c[p] == 1) {
        return INT_MAX;
    }
    vector<bool> d(0);
    for(int i = p; i < 31; i++) {
        d.push_back(c[i]);
    }
    for(int i = 0; i < p; i++) {
        d.push_back(c[i]);
    }
    int br = 0,y = 1;
    while(y < 31) {
        for(int i = 0; i < min(31,y); i++) {
            if(d[i] == 0) {
                y++;
            }
        }
        br++;
    }
    return br;
}

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;
    for(int i = 0; i < 31; i+=2) {
        int x = calc(c,i);
        if(x < sm) {
            sm = x;
            p = i;
        }
    }
    for(int i = 0; i < 4; i++) {
        vector<bool> wut(31);
        if((1 << (i+1))&p) {
            for(int j = 0; j < 31; j++) {
                wut[j] = 1;
            }
        }
        send_packet(wut);
    }
    int y = 1,z = 0;
    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 p = 0;
    for(int i = 0; i < 4; i++) {
        int br = 0;
        for(int j = 0; j < 31; j++) {
            if(r[i][j]) {
                br++;
            }
        }
        if(br >= 16) {
            p+=(1 << (i+1));
        }
    }
    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);
    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: 8.1451 / 10
• Subtask 2: 73.3056 / 90