oj.uz

Submission #1099804

# Submission time Handle Problem Language Result Execution time Memory
1099804 2024-10-12T05:21:10 Z model_code Message (IOI24_message) C++17
10 / 100
 971 ms 868 KB 
// incorrect/badawy_hashing_m_3_not_optimized.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;
}

bool get_bit(vector<bool> &msg, int ind)
{
    if(ind<10) return ((msg.size() >> ind) & 1);
    ind-=10;
    if(ind<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<allies.size();j++) {
            cur[allies[j]] = get_bit(message, msg_pos++);
        }
        cur_bits.push_back(send_packet(cur));
        known = get_known_allies();
        if(known.size() == 1) break;
    }
    assert(known[0] == allies[0]);
    for(int i=0;i<positions.size()-1;i++)
    {
        vector<bool> cur(BITS, 0);
        cur[known[0]] = positions[i];
        for(int j=1;j<allies.size();j++) {
            cur[allies[j]] = get_bit(message, msg_pos++);
        }
        send_packet(cur);
    }
    while(msg_pos<message.size()+10)
    {
        vector<bool> cur(BITS, 0);
        for(int j=0;j<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<received_bits.size();i++)
    {
        cur_bits.push_back(received_bits[i]);
        allies = get_known_allies();
        st++;
        if(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(allies.size()==16);
    vector<int> msg;
    for(int i=0;i<received_bits.size();i++)
    {
        for(int j=(i<st?1:0);j<allies.size();j++)
        {
            msg.push_back(received_bits[i][allies[j]]);
        }
    }
    int msglen = 0;
    for(int i=0;i<10;i++) msglen |= (msg[i]<<i);
    vector<bool> ret;
    assert(10+msglen <= msg.size());
    for(int i=10;i<10+msglen;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 'bool get_bit(std::vector<bool>&, int)':
message.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(ind<msg.size()) return msg[ind];
      |        ~~~^~~~~~~~~~~
message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=1;j<allies.size();j++) {
      |                     ~^~~~~~~~~~~~~~
message.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<positions.size()-1;i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
message.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=1;j<allies.size();j++) {
      |                     ~^~~~~~~~~~~~~~
message.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     while(msg_pos<message.size()+10)
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~
message.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j=0;j<allies.size();j++) {
      |                     ~^~~~~~~~~~~~~~
message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<received_bits.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
message.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<received_bits.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
message.cpp:112:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int j=(i<st?1:0);j<allies.size();j++)
      |                              ~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from message.cpp:5:
message.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     assert(10+msglen <= msg.size());
      |            ~~~~~~~~~~^~~~~~~~~~~~~

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 695 ms 848 KB Used 45 days
2 Correct 684 ms 852 KB Used 46 days
3 Correct 720 ms 844 KB Used 44 days
4 Correct 682 ms 844 KB Used 50 days
5 Correct 564 ms 868 KB Used 44 days
6 Correct 351 ms 864 KB Used 43 days
7 Correct 451 ms 852 KB Used 43 days

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Used 33 days
2 Correct 695 ms 848 KB Used 45 days
3 Correct 684 ms 852 KB Used 46 days
4 Correct 720 ms 844 KB Used 44 days
5 Correct 682 ms 844 KB Used 50 days
6 Correct 564 ms 868 KB Used 44 days
7 Correct 351 ms 864 KB Used 43 days
8 Correct 451 ms 852 KB Used 43 days
9 Incorrect 971 ms 416 KB decoded message is incorrect
10 Halted 0 ms 0 KB -