// partially_correct/solution.cpp
#include "message.h"
#include <bits/stdc++.h>
using namespace std;
/*
* The solution start by identifing one on allies in 4 rounds
* There will be 16+8+4+2 = 30 wasted bits and 16*4-30 = 34 bits that can be used to transmit the message
* Use 5 of them to indicate the number of bits you need to remove from the message. (29 bits remaining)
* in 29 rounds you can send for each bit whether it's ally or spy and use the remaining bits for the message
* You can skip the ally you already know and the last bit is already known so you need exactly 29 more rounds.
* If the message will take partial bits from 29 rounds we send [11111] [len of actual message],
* otherwise 5 bits are enough to indicate number of needed bits to be removed.
*/
const int BITS=31;
void send_message(std::vector<bool> message, std::vector<bool> positions) {
vector<int> cur_subset(BITS), cur_allies, free_allies;
iota(cur_subset.begin(), cur_subset.end(), 0);
for(int i=0;i<BITS;i++)
if(positions[i]==0) cur_allies.push_back(i);
int free_bits=(16*4-(16+8+4+2 + 5));
vector<bool> sent_bits;
if ((int)message.size() <= free_bits - 9 + 29*15) {
for(int i=0;i<5;i++) sent_bits.push_back(1);
int msg_len = message.size();
for(int i=0;i<9;i++) {
sent_bits.push_back(msg_len%2);
msg_len/=2;
}
for(int i=0;i<(int)message.size();i++) sent_bits.push_back(message[i]);
while((int)sent_bits.size() < free_bits + 29*15) sent_bits.push_back(0);
} else {
int rounds = ((int)message.size() + 5 + 15) / 16;
int remove_bits = rounds*16 - (message.size()), tmp_rem=remove_bits;
for(int i=0;i<5;i++) {
sent_bits.push_back(tmp_rem%2);
tmp_rem/=2;
}
for(int i=0;i<(int)message.size();i++) sent_bits.push_back(message[i]);
while(sent_bits.size() % 16) {sent_bits.push_back(0);}
}
int cur_pos = 0;
for(int _=0;_<4;_++)
{
vector<bool> msg(BITS);
for(int x=0;x<(int)cur_allies.size()/2;x++) msg[cur_allies[x]]=0;
for(int x=cur_allies.size()/2;x<(int)cur_allies.size();x++) msg[cur_allies[x]]=1;
sort(free_allies.begin(), free_allies.end());
for(int i:free_allies)
msg[i] = sent_bits[cur_pos++];
msg=send_packet(msg);
int co[2]={};
for(int i:cur_subset) co[msg[i]]++;
int used_bit = co[0]<co[1]? 0 : 1;
vector<int> new_subset, new_allies;
for(int i:cur_subset) {
if(msg[i] == used_bit) new_subset.push_back(i);
}
for(int i:cur_allies) {
if(msg[i] == used_bit) new_allies.push_back(i);
else free_allies.push_back(i);
}
cur_subset = new_subset;
cur_allies = new_allies;
}
assert(cur_allies.size() == 1);
int known_ally = cur_allies[0];
vector<bool> allies_positions;
for(int i=0;i<BITS;i++)
{
if(i==known_ally) continue;
allies_positions.push_back(positions[i]);
}
allies_positions.pop_back();
for(int i=0;i<29;i++) {
vector<bool> msg(BITS);
for(int x=0;x<BITS;x++)
{
if(x==known_ally) msg[x]=allies_positions[i];
else if(positions[x]==0)
msg[x] = sent_bits[cur_pos++];
}
send_packet(msg);
}
while(cur_pos < (int)sent_bits.size()) {
vector<bool> msg(BITS);
for(int i=0;i<BITS;i++) {
if(positions[i]==0)
msg[i]=sent_bits[cur_pos++];
}
send_packet(msg);
}
}
std::vector<bool> receive_message(vector<vector<bool>> received_bits) {
vector<int> cur_subset(BITS);
iota(cur_subset.begin(),cur_subset.end(), 0);
for(int r=0;r<4;r++) {
int co[2]={};
for(int i:cur_subset) co[received_bits[r][i]]++;
int used_bit = co[0]<co[1]? 0 : 1;
vector<int> new_subset;
for(int i:cur_subset)
if(received_bits[r][i] == used_bit) new_subset.push_back(i);
cur_subset = new_subset;
}
assert(cur_subset.size() == 1);
int known_ally = cur_subset[0];
vector<bool> positions;
int cur_ally=0, curtotal=15;
for(int i=4;i<4+29;i++) {
if(cur_ally == known_ally) {
positions.push_back(0); cur_ally++;
}
positions.push_back(received_bits[i][known_ally]);
cur_ally++; curtotal -= positions.back();
}
if(cur_ally==known_ally) positions.push_back(0); // Position before last is known ally
positions.push_back(curtotal);
if(positions.size()<31) positions.push_back(0); // Last position is known ally
vector<int> ally_positions;
for(int i=0;i<BITS;i++)
if(positions[i]==0) ally_positions.push_back(i);
vector<bool> msg;
cur_subset = vector<int>(BITS);
iota(cur_subset.begin(),cur_subset.end(), 0);
for(int r=0;r<4;r++) {
int bad[BITS]={};
int co[2]={};
for(int i:cur_subset) {bad[i] = 1; co[received_bits[r][i]]++;}
int used_bit = co[0]<co[1]? 0 : 1;
vector<int> new_subset;
for(int i:cur_subset) {
if(received_bits[r][i] == used_bit) {
new_subset.push_back(i);
}
}
cur_subset = new_subset;
for(int i:ally_positions)
if(!bad[i]) msg.push_back(received_bits[r][i]);
}
for(int i=4;i<4+29;i++) {
for(int j:ally_positions) {
if(j==known_ally) continue;
msg.push_back(received_bits[i][j]);
}
}
for(int i=4+29;i<(int)received_bits.size();i++) {
for(int j:ally_positions) msg.push_back(received_bits[i][j]);
}
int case1=1;
for(int i=0;i<5;i++) case1&=msg[i];
if(case1) {
int len=0;
for(int i=9+5-1;i>=5;i--) {
len*=2; len+=msg[i];
}
vector<bool> res;
for(int i=9+5;i<9+5+len;i++)
res.push_back(msg[i]);
return res;
} else {
vector<bool> cur_msg;
for(int i=5;i<(int)msg.size();i++) cur_msg.push_back(msg[i]);
int rem=0;
for(int i=4;i>=0;i--) {
rem*=2; rem+=msg[i];
}
while(rem--) cur_msg.pop_back();
return cur_msg;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
664 KB |
Used 33 days |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
418 ms |
1060 KB |
Used 33 days |
| 2 |
Correct |
475 ms |
1060 KB |
Used 33 days |
| 3 |
Correct |
438 ms |
796 KB |
Used 33 days |
| 4 |
Correct |
452 ms |
816 KB |
Used 33 days |
| 5 |
Correct |
310 ms |
800 KB |
Used 33 days |
| 6 |
Correct |
277 ms |
1052 KB |
Used 33 days |
| 7 |
Correct |
261 ms |
804 KB |
Used 33 days |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
664 KB |
Used 33 days |
| 2 |
Correct |
418 ms |
1060 KB |
Used 33 days |
| 3 |
Correct |
475 ms |
1060 KB |
Used 33 days |
| 4 |
Correct |
438 ms |
796 KB |
Used 33 days |
| 5 |
Correct |
452 ms |
816 KB |
Used 33 days |
| 6 |
Correct |
310 ms |
800 KB |
Used 33 days |
| 7 |
Correct |
277 ms |
1052 KB |
Used 33 days |
| 8 |
Correct |
261 ms |
804 KB |
Used 33 days |
| 9 |
Partially correct |
919 ms |
824 KB |
Used 69 days |
| 10 |
Partially correct |
599 ms |
832 KB |
Used 68 days |
| 11 |
Partially correct |
860 ms |
1052 KB |
Used 69 days |
| 12 |
Partially correct |
899 ms |
816 KB |
Used 68 days |
| 13 |
Partially correct |
824 ms |
1060 KB |
Used 68 days |
| 14 |
Partially correct |
650 ms |
800 KB |
Used 69 days |
| 15 |
Partially correct |
503 ms |
820 KB |
Used 69 days |
| 16 |
Partially correct |
656 ms |
800 KB |
Used 69 days |
| 17 |
Partially correct |
661 ms |
796 KB |
Used 68 days |
| 18 |
Correct |
463 ms |
976 KB |
Used 33 days |
| 19 |
Correct |
447 ms |
816 KB |
Used 33 days |
| 20 |
Correct |
493 ms |
1068 KB |
Used 33 days |
| 21 |
Correct |
428 ms |
808 KB |
Used 33 days |
| 22 |
Correct |
507 ms |
1052 KB |
Used 36 days |
| 23 |
Correct |
581 ms |
1056 KB |
Used 42 days |
| 24 |
Correct |
658 ms |
1060 KB |
Used 49 days |
| 25 |
Correct |
665 ms |
796 KB |
Used 55 days |
| 26 |
Correct |
733 ms |
828 KB |
Used 61 days |
| 27 |
Partially correct |
816 ms |
792 KB |
Used 67 days |
| 28 |
Partially correct |
808 ms |
824 KB |
Used 69 days |
