제출 #1177198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177198		madamadam3	메시지 (IOI24_message)	C++20	43.96 / 100	469 ms	864 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;

using vb = vector<bool>;
using vvb = vector<vb>;

// strategy 1 (should get 10 points for S <= 64)
// send S packets. if the majority of bits in a packet are 1, then M[i] = 1. else M[i] = 0
// we have 16 (majority) of bits to ourself, so strat always works

// strategy 2 (should get 29 ish points)
// same as strat 1, except we broadcast which bits are fine and which arent
// 31 messages to inform + 65 messages to broadcast = 96 total

// M = message to send, len(M) <= 1024
// C = bitmask of tainted bits, len(C) = 31
// if C[i] = 0, then that bit is safe, otherwise that bit isnt
// 15 unsafe, 16 safe

vb mask(vb C, vb bits, int has) {
  while (bits.size() < has) bits.push_back(false);

  int idx = 0;
  vb ans(31, false);
  for (int i = 0; i < 31; i++) {
    if (!C[i]) {
      ans[i] = bits[idx];
      idx++;
    }
  }

  return ans;
}

vb decode(vb C, vb bits, int bitsAvail) {
  vb M;
  int bitsused = 0;
  for (int i = 0; i < 31; i++) {
    if (!C[i]) {
      M.push_back(bits[i]);
      bitsused++;
    }
    if (bitsused >= bitsAvail) break;
  }

  return M;
}

vb int_to_vb(int inp) {
  vb ans(16, false);
  for (int i = 0; i < 16; i++) {
    ans[i] = inp & (1 << i);
  }
  return ans;
}

int vb_to_int(vb inp) {
  int ans = 0;
  for (int i = 0; i < 16; i++) {
    if (inp[i]) ans |= 1 << i;
  }

  return ans;
}

void trace_vb(vb inp) {
  for (int i = 0; i < (int) inp.size(); i++) {
    cout << (inp[i] ? "1 " : "0 ");
  }
  cout << "\n";
}

void send_message(vb M, vb C) {
  int S = (int) M.size();
  vb ZERO = vb(31, false);
  vb ONE = vb(31, true);

  vb curMask(31, true);
  int firstUs = 0, bitsAvail = 0;

  for (int i = 0; i < 31; i++) {
    if (C[i] == false) {
      send_packet(ZERO);
      curMask[i] = false;
      firstUs = i;
      bitsAvail++;
      break;
    } else {
      send_packet(ONE);
    }
  }

  for (int i = firstUs + 1; i < 31; i++) {
    vb nextmask;
    int oldba = bitsAvail;
    for (int j = i; j < i + oldba && j < 31; j++) {
      if (!C[j]) {
        bitsAvail++;
        nextmask.push_back(true);
      } else {
        nextmask.push_back(false);
      }
    }

    send_packet(mask(C, nextmask, oldba));
    i += oldba - 1;
  }

  send_packet(mask(C, int_to_vb(S), bitsAvail));

  vb cur(16, false);
  for (int i = 0; i < S; i++) {
    cur[i % 16] = M[i];

    if ((i + 1) % 16 == 0 || i == S - 1) {
      send_packet(mask(C, cur, bitsAvail));
      cur = vb(16, false);
    }
  }
}

vb receive_message(vvb R) {
  int packets = (int) R.size();
  vb safe(31, true);
  vb M;

  int first_safe = 0;
  int bitsAvail = 0;
  for (int i = 0; i < 31; i++) {
    int ZEROS = 0; for (int j = 0; j < 31; j++) ZEROS += R[i][j] == false;
    if (ZEROS >= 16) {
      first_safe = i;
      bitsAvail++;
      safe[i] = false;
      break;
    }
  }

  int cur_bit = first_safe + 1;
  int last_packet = first_safe;
  for (int i = first_safe + 1; cur_bit < 31; i++) {
    int oldba = bitsAvail;
    vb has = decode(safe, R[i], oldba);

    for (int j = 0; j < oldba; j++) {
      if (has[j]) bitsAvail++;
      safe[cur_bit + j] = !has[j];
    }
    cur_bit += oldba;
    last_packet = i+1;
  }

  int length = vb_to_int(decode(safe, R[last_packet], bitsAvail));

  for (int i = last_packet+1; i < packets; i++) {
    vb out = decode(safe, R[i], bitsAvail);
    for (bool el : out) {
      M.push_back(el);
    }
  }

  vb nM;
  for (int i = 0; i < length; i++) nM.push_back(M[i]);
  return nM;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 33.9618 / 90