oj.uz

Submission #1099809

# Submission time Handle Problem Language Result Execution time Memory
1099809 2024-10-12T05:22:08 Z model_code Message (IOI24_message) C++17
42.2637 / 100
 1224 ms 1280 KB 
// partially_correct/badawy_hashing_index.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<cur_bits.size();j++)
            cur+=cur_bits[j][i]+'0';
        if(cur==known_pattern[i].substr(0, cur_bits.size())) ret.push_back(i);
    }
    return ret;
}

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;
    for(int i=0;i<100;i++)
    {
        vector<bool> cur(BITS, 0);
        for(int j=0;j<allies.size();j++) cur[allies[j]]=known_pattern[allies[j]][i]-'0';
        cur_bits.push_back(send_packet(cur));
        known = get_known_allies();
        if(known.size() == 16) break;
    }
    vector<int> msg;
    int rem=(16 - (4+message.size())%16)%16;
    for(int i=0;i<4;i++) msg.push_back((rem&(1<<i)) > 0);
    for(int i:message) msg.push_back(i);
    int msg_pos = 0;
    while(msg_pos < msg.size())
    {
        vector<bool> cur(BITS, 0);
        for(int i:allies) {
            cur[i]=(msg_pos < msg.size()? msg[msg_pos] : 0);
            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<received_bits.size();i++)
    {
        cur_bits.push_back(received_bits[i]);
        allies = get_known_allies();
        st++;
        if(allies.size() == 16) break;
    }
    vector<int> msg;
    while(st<received_bits.size())
    {
        for(int i:allies) msg.push_back(received_bits[st][i]);
        st++;
    }
    int rem=0;
    for(int i=0;i<4;i++) if(msg[i]) rem|=(1<<i);
    while(rem--) msg.pop_back();
    vector<bool> ret;
    for(int i=4;i<msg.size();i++) ret.push_back(msg[i]);
    return ret;
}

Compilation message

message.cpp: In function 'std::vector<int> get_known_allies()':
message.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j=0;j<cur_bits.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j=0;j<allies.size();j++) cur[allies[j]]=known_pattern[allies[j]][i]-'0';
      |                     ~^~~~~~~~~~~~~~
message.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while(msg_pos < msg.size())
      |           ~~~~~~~~^~~~~~~~~~~~
message.cpp:56:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             cur[i]=(msg_pos < msg.size()? msg[msg_pos] : 0);
      |                     ~~~~~~~~^~~~~~~~~~~~
message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<received_bits.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
message.cpp:82:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     while(st<received_bits.size())
      |           ~~^~~~~~~~~~~~~~~~~~~~~
message.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=4;i<msg.size();i++) ret.push_back(msg[i]);
      |                 ~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 836 KB Used 18 days
2 Correct 343 ms 840 KB Used 19 days
3 Correct 361 ms 852 KB Used 20 days
4 Correct 298 ms 1100 KB Used 23 days
5 Correct 272 ms 832 KB Used 18 days
6 Correct 176 ms 820 KB Used 19 days
7 Correct 193 ms 844 KB Used 18 days

Subtask #2
32.263733016 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 4 days
2 Correct 373 ms 836 KB Used 18 days
3 Correct 343 ms 840 KB Used 19 days
4 Correct 361 ms 852 KB Used 20 days
5 Correct 298 ms 1100 KB Used 23 days
6 Correct 272 ms 832 KB Used 18 days
7 Correct 176 ms 820 KB Used 19 days
8 Correct 193 ms 844 KB Used 18 days
9 Partially correct 1224 ms 876 KB Used 81 days
10 Partially correct 769 ms 884 KB Used 75 days
11 Partially correct 1183 ms 1084 KB Used 81 days
12 Partially correct 1131 ms 856 KB Used 86 days
13 Partially correct 1164 ms 1076 KB Used 79 days
14 Partially correct 874 ms 1032 KB Used 81 days
15 Partially correct 616 ms 1088 KB Used 80 days
16 Partially correct 948 ms 872 KB Used 79 days
17 Partially correct 854 ms 860 KB Used 82 days
18 Correct 333 ms 856 KB Used 20 days
19 Correct 427 ms 848 KB Used 26 days
20 Correct 525 ms 1080 KB Used 31 days
21 Correct 624 ms 1280 KB Used 38 days
22 Correct 677 ms 1240 KB Used 48 days
23 Correct 808 ms 856 KB Used 50 days
24 Correct 860 ms 876 KB Used 59 days
25 Correct 954 ms 856 KB Used 63 days
26 Partially correct 1042 ms 1020 KB Used 69 days
27 Partially correct 1119 ms 860 KB Used 77 days
28 Partially correct 1105 ms 1100 KB Used 82 days