Submission #1177333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177333		ErJ	Message (IOI24_message)	C++20	76.16 / 100	425 ms	856 KiB

message

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define vb vector<bool>

vector<vb> ANS;

std::vector<bool> send_packet(std::vector<bool> A);


/*std::vector<bool> send_packet(std::vector<bool> A){
    ANS.push_back(A);
    return A;
}*/


vb zero(31, false), one(31, true);

void sendBit(bool x){
    if(x) send_packet(one);
    else send_packet(zero);
}

void sendAll(vb C, vb M){
    ll ind = 0;
    vb now = zero;
    ll Cind = 0;
    while(ind < M.size()){
        if(Cind >= zero.size()){
            send_packet(now);
            now = zero;
            Cind = 0;
        }else{
            if(C[Cind] == 1){
                Cind++;
            }else{
                now[Cind] = M[ind];
                ind++;
                Cind++;
            }
        }
    }
    send_packet(now);
    now = zero;
    for(int i = 0; i < Cind; i++){
        now[i] = 1;
    }
    send_packet(now); // end checker
}

void smartSendAll(vb M, vb C, ll firstZero){
    ll ind = 0;
    vb now = zero;
    ll Cind = 0;
    ll mask = 0;
    while(ind < M.size()){
        if(Cind >= zero.size()){
            send_packet(now);
            now = zero;
            Cind = 0;
        }else{
            if(C[Cind] == 1){
                Cind++;
            }else{
                if(Cind == firstZero && mask < C.size()){
                    now[Cind] = C[mask];
                    mask++;
                    Cind++;
                }else{
                    now[Cind] = M[ind];
                    ind++;
                    Cind++;
                }
            }
        }
    }
    send_packet(now);
    now = zero;
    for(int i = 0; i < Cind; i++){
        now[i] = 1;
    }
    send_packet(now); // end checker
}

void send_message(std::vector<bool> M, std::vector<bool> C){
    /*for(int i = 0; i < C.size(); i++){
        sendBit(C[i]);
    }
    sendAll(C, M);*/
    if(M.size() <= 495){
        sendBit(1);
        for(int i = 0; i < C.size(); i++){
            sendBit(C[i]);
        }
        sendAll(C, M);
    }else {
        sendBit(0);
        ll firstZero = 0;
        for(int i = 0; i < C.size(); i++){
            if(!C[i]){
                firstZero = i;
                break;
            }
        }
        sendBit(firstZero & 1);
        sendBit(firstZero & 2);
        sendBit(firstZero & 4);
        sendBit(firstZero & 8);
        smartSendAll(M, C, firstZero);
    }
}

bool getBit(vb packet){
    ll ones = 0;
    ll zeros = 0;
    for(int i = 0; i < packet.size(); i++){
        if(packet[i] == 0) zeros++;
        else ones++;
    }
    if(ones > zeros) return 1;
    else return 0;
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R){
    bool stupid = getBit(R[0]);
    vb ans;
    if(stupid){
        vb C(31);
        for(int i = 1; i < C.size() + 1; i++){
            C[i - 1] = getBit(R[i]);
        }
        for(int i = C.size() + 1; i < R.size() - 2; i++){
            for(int j = 0; j < C.size(); j++){
                if(C[j] == 0){
                    ans.push_back(R[i][j]);
                }
            }
        }
        for(int j = 0; j < C.size(); j++){
            if((C[j] == 0) && (R.back()[j] == 1)){
                ans.push_back(R[R.size() - 2][j]);
            }
        }
    }else{
        ll fisrtZero = 0;
        ll ind = 1;
        for(int i = 1; i < 16; i *= 2){
            if(getBit(R[ind])) fisrtZero += i;
            ind++;
        }
        vi C(31);
        for(int i = 0; i < C.size(); i++){
            C[i] = R[ind + i][fisrtZero];
        }
        for(int i = ind; i < ind + C.size(); i++){
            for(int j = 0; j < C.size(); j++){
                if(j != fisrtZero){
                    if(C[j] == 0){
                        ans.push_back(R[i][j]);
                    }
                }
            }
        }
        ind += C.size();
        for(int i = ind; i < R.size() - 2; i++){
            for(int j = 0; j < C.size(); j++){
                if(C[j] == 0){
                    ans.push_back(R[i][j]);
                }
            }
        }
        for(int j = 0; j < C.size(); j++){
            if((C[j] == 0) && (R.back()[j] == 1)){
                ans.push_back(R[R.size() - 2][j]);
            }
        }
    }
    
    /*for(int i = 0; i < R.size(); i++){
        ans.push_back(getBit(R[i]));
    }*/
    return ans;
}
/*
int main(){
    send_message({0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0,
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0,
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 
    0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0}, 
    {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    );
    vb gg = receive_message(ANS);
    for(int i = 0; i < gg.size(); i++){
        cout << gg[i] << " ";
    }
    cout << '\n';
}
*/

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