oj.uz

Submission #1099802

# Submission time Handle Problem Language Result Execution time Memory
1099802 2024-10-12T05:20:46 Z model_code Message (IOI24_message) C++17
10 / 100
 1628 ms 1072 KB 
// incorrect/badawy_hashing.cpp

#include "message.h"

#include <bits/stdc++.h>

using namespace std;

const int BITS=31;

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

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

void send_message(vector<bool> message, vector<bool> positions) {
    srand(123456);
    for(int i=0;i<16;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[j][i]-'0';
        cur_bits.push_back(send_packet(cur));
        known = get_known_allies();
        if(known.size()) break;
    }
    assert(known.size());
    int al_pos=0;
    while(al_pos < positions.size()-1)
    {
        vector<bool> cur(BITS, 0);
        for(int i:known) {
            cur[i] = (al_pos<positions.size()-1?positions[al_pos]:0);
            al_pos++;
        }
        send_packet(cur);
    }
    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<16;i++)
    {
        known_pattern[i]="";
        for(int j=0;j<100;j++)
            known_pattern[i] += '0'+rand()%2;
    }
    int st=0;
    vector<int> known_allies;
    for(int i=0;i<received_bits.size();i++)
    {
        cur_bits.push_back(received_bits[i]);
        known_allies = get_known_allies();
        st++;
        if(known_allies.size()) break;
    }
    vector<int> pos;
    while(pos.size() < BITS-1)
    {
        for(int i:known_allies) pos.push_back(received_bits[st][i]);
        st++;
    }
    while(pos.size() > BITS-1) pos.pop_back();
    int curc = 15 - count(pos.begin(), pos.end(), 1);
    pos.push_back(curc);
    vector<int> allies;
    for(int i=0;i<BITS;i++) if(pos[i]==0) allies.push_back(i);
    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:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for(int k=0;k<cur_bits.size();k++) cur+=cur_bits[k][j]+'0';
      |                         ~^~~~~~~~~~~~~~~~
message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<allies.size();j++) cur[allies[j]]=known_pattern[j][i]-'0';
      |                     ~^~~~~~~~~~~~~~
message.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(al_pos < positions.size()-1)
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~
message.cpp:60:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             cur[i] = (al_pos<positions.size()-1?positions[al_pos]:0);
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~
message.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while(msg_pos < msg.size())
      |           ~~~~~~~~^~~~~~~~~~~~
message.cpp:74:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             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:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<received_bits.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
message.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while(st<received_bits.size())
      |           ~~^~~~~~~~~~~~~~~~~~~~~
message.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     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 2 ms 664 KB Used 19 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 840 KB Used 40 days
2 Correct 727 ms 852 KB Used 39 days
3 Correct 671 ms 852 KB Used 40 days
4 Correct 671 ms 844 KB Used 39 days
5 Correct 537 ms 1072 KB Used 41 days
6 Correct 406 ms 816 KB Used 40 days
7 Correct 437 ms 848 KB Used 39 days

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Used 19 days
2 Correct 721 ms 840 KB Used 40 days
3 Correct 727 ms 852 KB Used 39 days
4 Correct 671 ms 852 KB Used 40 days
5 Correct 671 ms 844 KB Used 39 days
6 Correct 537 ms 1072 KB Used 41 days
7 Correct 406 ms 816 KB Used 40 days
8 Correct 437 ms 848 KB Used 39 days
9 Partially correct 1571 ms 876 KB Used 100 days
10 Partially correct 1213 ms 880 KB Used 98 days
11 Partially correct 1628 ms 880 KB Used 100 days
12 Partially correct 1524 ms 860 KB Used 99 days
13 Partially correct 1531 ms 860 KB Used 99 days
14 Incorrect 22 ms 332 KB Used too many days
15 Halted 0 ms 0 KB -