oj.uz

Submission #1099800

# Submission time Handle Problem Language Result Execution time Memory
1099800 2024-10-12T05:20:23 Z model_code Message (IOI24_message) C++17
10 / 100
 1063 ms 1092 KB 
// incorrect/badawy_use_known_optimized.cpp

#include "message.h"

#include <iostream>
#include <vector>
#include <algorithm>

const int LG=17, POS=31;
using namespace std;

vector<vector<bool> > sent_items;

void send(int &ind, vector<int> &kn,vector<bool> sent, bool rev) {
    if(kn.size() == 0) {
        vector<bool> cur(POS, sent[ind]);
        if(sent[ind] == 0) kn.push_back((rev? POS-ind-1:ind));
        ind++;
        sent_items.push_back(cur);
    } else {
        vector<int> tba;
        vector<bool> cur(POS);
        for(int i=0;i<kn.size();i++) {
            if(ind+i < POS && sent[ind+i] == 0) {
                tba.push_back((rev? POS-(ind+i) -1 : ind+i));
            }
            cur[kn[i]] = (ind+i < sent.size() ? sent[ind+i] : 0);
        }
        ind+=kn.size();
        sent_items.push_back(cur);
        for(int i:tba)
            kn.push_back(i);
    }
}

void send_message(std::vector<bool> message, std::vector<bool> positions) {
    vector<bool> sent;
    for(int i=0;i<positions.size();i++)
        sent.push_back(positions[i]);
    int len=message.size();
    for(int i=0;i<10;i++) sent.push_back((len>>i)&1);
    for(int i=0;i<message.size();i++)  sent.push_back(message[i]);
    vector<int> kn;
    int ind=0; sent_items.clear();
    while(ind<sent.size()) {
        send(ind, kn, sent, 0);
    }
    reverse(sent.begin(), sent.begin()+positions.size());
    vector<vector<bool> > cur=sent_items;
    ind=0; kn.clear();
    sent_items.clear();
    while(ind<sent.size()) {
        send(ind, kn, sent, 1);
    }
    if(cur.size()<sent_items.size()) {
        send_packet(vector<bool>(POS, 0));
        for(auto i:cur) send_packet(i);
    } else {
        send_packet(vector<bool>(POS, 1));
        for(auto i:sent_items) send_packet(i);
    }
    cerr << cur.size() << " " << sent_items.size() << endl;
}

void receive(vector<int> &kn, vector<bool> &msg, vector<bool> received, bool rev) {
    if(kn.size() == 0) {
        sort(received.begin(), received.end());
        msg.push_back(received[15]);
        if(msg.back() == 0) {
            kn.push_back(rev? POS- (msg.size() - 1) - 1 : msg.size()-1);
        }
    } else {
        vector<int> tba;
        for(int i=0;i<kn.size();i++) {
            msg.push_back(received[kn[i]]);
            if(msg.back()==0 && msg.size() <= POS) {
                tba.push_back(rev? POS- (msg.size() - 1) - 1 : msg.size()-1);
            }
        }
        for(int i:tba) kn.push_back(i);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> received_bits) {
    vector<bool> msg;
    vector<int> kn;
    sort(received_bits[0].begin(), received_bits[0].end());
    bool rev=received_bits[0][15];
    for(int i=1;i<received_bits.size();i++) receive(kn, msg, received_bits[i], rev);
    int len=0;
    for(int i=POS;i<POS+10;i++) len|=msg[i]<<(i-POS);
    vector<bool> rel;
    for(int i=POS+10;i<msg.size();i++) rel.push_back(msg[i]);
    while(rel.size() > len) rel.pop_back();
    return rel;
}

Compilation message

message.cpp: In function 'void send(int&, std::vector<int>&, std::vector<bool>, bool)':
message.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=0;i<kn.size();i++) {
      |                     ~^~~~~~~~~~
message.cpp:27:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             cur[kn[i]] = (ind+i < sent.size() ? sent[ind+i] : 0);
      |                           ~~~~~~^~~~~~~~~~~~~
message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<positions.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
message.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<message.size();i++)  sent.push_back(message[i]);
      |                 ~^~~~~~~~~~~~~~~
message.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(ind<sent.size()) {
      |           ~~~^~~~~~~~~~~~
message.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while(ind<sent.size()) {
      |           ~~~^~~~~~~~~~~~
message.cpp: In function 'void receive(std::vector<int>&, std::vector<bool>&, std::vector<bool>, bool)':
message.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i=0;i<kn.size();i++) {
      |                     ~^~~~~~~~~~
message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=1;i<received_bits.size();i++) receive(kn, msg, received_bits[i], rev);
      |                 ~^~~~~~~~~~~~~~~~~~~~~
message.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=POS+10;i<msg.size();i++) rel.push_back(msg[i]);
      |                      ~^~~~~~~~~~~
message.cpp:94:22: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     while(rel.size() > len) rel.pop_back();
      |           ~~~~~~~~~~~^~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1092 KB Used 17 days
2 Correct 182 ms 844 KB Used 15 days
3 Correct 234 ms 840 KB Used 16 days
4 Correct 286 ms 852 KB Used 15 days
5 Correct 178 ms 1088 KB Used 17 days
6 Correct 127 ms 836 KB Used 16 days
7 Correct 122 ms 824 KB Used 16 days

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 664 KB Used 8 days
2 Correct 256 ms 1092 KB Used 17 days
3 Correct 182 ms 844 KB Used 15 days
4 Correct 234 ms 840 KB Used 16 days
5 Correct 286 ms 852 KB Used 15 days
6 Correct 178 ms 1088 KB Used 17 days
7 Correct 127 ms 836 KB Used 16 days
8 Correct 122 ms 824 KB Used 16 days
9 Incorrect 1063 ms 444 KB decoded message is incorrect
10 Halted 0 ms 0 KB -