oj.uz

Submission #1099818

# Submission time Handle Problem Language Result Execution time Memory
1099818 2024-10-12T05:23:56 Z model_code Message (IOI24_message) C++17
91.225 / 100
 1143 ms 1088 KB 
// partially_correct/badawy_hashing_m_3.cpp

#include "message.h"

#include <bits/stdc++.h>

using namespace std;

const int BITS=31;

string known_pattern[BITS];
vector<vector<bool>> cur_bits;

vector<int> get_known_allies()
{
    vector<int> ret;
    for(int i=0;i<BITS;i++)
    {
        string cur="";
        for(int j=0;j<(int)cur_bits.size();j++)
            cur+=cur_bits[j][i]+'0';
        if(cur==known_pattern[i].substr(0, (int)cur_bits.size())) ret.push_back(i);
    }
    return ret;
}

bool get_bit(vector<bool> &msg, int ind)
{
    if((int)msg.size()<750)
    {
        if(ind==0) return 1;
        ind--;
        if(ind<10) return (((int)msg.size() >> ind) & 1);
        ind-=10;
        if(ind<(int)msg.size()) return msg[ind];
        return 0;
    }
    int x=(int)msg.size()%16;
    if(ind==0) return 0;
    ind--;
    if(ind<4) return ((x >> ind) & 1);
    ind-=4;
    if(ind<(int)msg.size()) return msg[ind];
    return 0;
}

void send_message(vector<bool> message, vector<bool> positions) {
    srand(123456);
    for(int i=0;i<BITS;i++)
    {
        known_pattern[i]="";
        for(int j=0;j<100;j++)
            known_pattern[i] += '0'+rand()%2;
    }
    cur_bits.clear();
    vector<int> allies;
    for(int i=0;i<BITS;i++) if(positions[i]==0) allies.push_back(i);
    vector<int> known;
    int msg_pos=0;
    for(int i=0;i<100;i++)
    {
        vector<bool> cur(BITS, 0);
        cur[allies[0]] = known_pattern[allies[0]][i] - '0';
        for(int j=1;j<(int)allies.size();j++) {
            cur[allies[j]] = get_bit(message, msg_pos++);
        }
        cur_bits.push_back(send_packet(cur));
        known = get_known_allies();
        if((int)known.size() == 1) break;
    }
    assert(known[0] == allies[0]);
    for(int i=0;i<(int)positions.size()-1;i++)
    {
        vector<bool> cur(BITS, 0);
        cur[known[0]] = positions[i];
        for(int j=1;j<(int)allies.size();j++) {
            cur[allies[j]] = get_bit(message, msg_pos++);
        }
        send_packet(cur);
    }
    while(msg_pos<(int)message.size()+((int)message.size()<750?11:5))
    {
        vector<bool> cur(BITS, 0);
        for(int j=0;j<(int)allies.size();j++) {
            cur[allies[j]] = get_bit(message, msg_pos++);
        }
        send_packet(cur);
    }
}

vector<bool> receive_message(vector<vector<bool>> received_bits) {
    srand(123456);
    cur_bits.clear();
    for(int i=0;i<BITS;i++)
    {
        known_pattern[i]="";
        for(int j=0;j<100;j++)
            known_pattern[i] += '0'+rand()%2;
    }
    int st=0;
    vector<int> allies;
    for(int i=0;i<(int)received_bits.size();i++)
    {
        cur_bits.push_back(received_bits[i]);
        allies = get_known_allies();
        st++;
        if((int)allies.size() == 1) break;
    }
    vector<bool> pos;
    int curc=15;
    for(int i=0;i<BITS-1;i++)
    {
        pos.push_back(received_bits[st][allies[0]]);
        curc-=pos.back();
        st++;
    }
    pos.push_back(curc);
    allies.clear();
    for(int i=0;i<BITS;i++) if(pos[i]==0) allies.push_back(i);
    assert((int)allies.size()==16);
    vector<int> msg;
    for(int i=0;i<(int)received_bits.size();i++)
    {
        for(int j=(i<st?1:0);j<(int)allies.size();j++)
        {
            msg.push_back(received_bits[i][allies[j]]);
        }
    }
    int msglen = 0;
    for(int i=1;i<=(msg[0]?10:4);i++) msglen |= (msg[i]<<(i-1));
    vector<bool> ret;
    if(msg[0]==0)
    {
        int curm = (int)msg.size()-5;
        while(curm%16 != msglen) curm--;
        msglen = curm;
    }
    for(int i=(msg[0]?11:5);i<(msg[0]?11:5)+msglen;i++) ret.push_back(msg[i]);
    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 33 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 1088 KB Used 46 days
2 Correct 660 ms 1080 KB Used 42 days
3 Correct 617 ms 992 KB Used 45 days
4 Correct 673 ms 1072 KB Used 46 days
5 Correct 455 ms 844 KB Used 44 days
6 Correct 356 ms 812 KB Used 44 days
7 Correct 482 ms 812 KB Used 44 days

Subtask #2
81.225 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 33 days
2 Correct 669 ms 1088 KB Used 46 days
3 Correct 660 ms 1080 KB Used 42 days
4 Correct 617 ms 992 KB Used 45 days
5 Correct 673 ms 1072 KB Used 46 days
6 Correct 455 ms 844 KB Used 44 days
7 Correct 356 ms 812 KB Used 44 days
8 Correct 482 ms 812 KB Used 44 days
9 Partially correct 1143 ms 856 KB Used 68 days
10 Correct 775 ms 848 KB Used 66 days
11 Partially correct 1065 ms 1000 KB Used 67 days
12 Partially correct 1049 ms 856 KB Used 67 days
13 Partially correct 1084 ms 812 KB Used 67 days
14 Partially correct 830 ms 848 KB Used 67 days
15 Partially correct 557 ms 988 KB Used 68 days
16 Partially correct 808 ms 860 KB Used 67 days
17 Partially correct 771 ms 852 KB Used 67 days
18 Correct 654 ms 848 KB Used 45 days
19 Correct 670 ms 852 KB Used 45 days
20 Correct 637 ms 844 KB Used 45 days
21 Correct 665 ms 852 KB Used 45 days
22 Correct 661 ms 812 KB Used 47 days
23 Correct 790 ms 820 KB Used 44 days
24 Correct 813 ms 812 KB Used 47 days
25 Correct 945 ms 844 KB Used 53 days
26 Correct 989 ms 820 KB Used 59 days
27 Correct 958 ms 1020 KB Used 66 days
28 Partially correct 1065 ms 856 KB Used 67 days