Submission #1165551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165551		iah	메시지 (IOI24_message)	C++20	83.31 / 100	411 ms	852 KiB

message

#include "message.h"
#include<bits/stdc++.h>
using namespace std;

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

void send_message(std::vector<bool> M, std::vector<bool> C) {
  int id = 0;
  REP(i, 16) {
    if (C[i] == 0) {
      id = i;
      break;
    }
  }

  REP(j, 4) {
    int i = bit(id, j);
    vector < bool > packet(31, i);
    send_packet(packet);
  }

  int pos = 0;

  M.push_back(M.back() ^ 1);

//  for (auto x: M) {
//    cout << x << " ";
//  }
//  cout << "\n";

  REP(i, 30) {
    if (i == id) {
      continue;
    }

    vector < bool > packet(31, 0);

    REP(j, 31) {
      if (C[j] == 1) {
        continue;
      }

      if (j == id) {
        packet[j] = C[i];
        continue;
      }

      pos = min(pos, sz(M) - 1);
//      if (i == 1) {
//        cout << pos << " " << j << "\n";
//      }
      packet[j] = M[pos];
      pos ++;
    }

//    cout << i << " " << sz(R) << "\n";

//    for (auto x: packet) {
//      cout << x << " ";
//    }
//    cout << "\n";

    send_packet(packet);
  }

  while (pos < sz(M)) {
    vector < bool > packet(31, 0);
    REP(j, 31) {
      if (C[j] == 1) {
        continue;
      }

      pos = min(pos, sz(M) - 1);
      packet[j] = M[pos];
      pos ++;
    }

    send_packet(packet);
  }
}

int cnt[2];

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  int pos = 0;
  REP(id, 4) {
    REP(j, 2) {
      cnt[j] = 0;
    }
    for (auto x: R[id]) {
      cnt[x] ++;
    }

    if (cnt[0] < cnt[1]) {
      pos ^= mask(id);
    }
  }

  vector < bool > ans;
  vector < bool > C(31, 0);

//  cout << sz(R) << "\n";

  for (int i = 0, j = 0; j < 30; j ++) {
    if (j == pos) {
      continue;
    }

    C[j] = R[i + 4][pos];

//    cout << j << " " << i << " " << R[i + 4][pos] << "\n";

    i ++;
  }

  REP(j, 2) {
    cnt[j] = 0;
  }

  for (auto x: C) {
    cnt[x] ++;
  }

  cnt[0] --;

  if (cnt[0] > cnt[1]) {
    C[30] = 1;
  }

//  for (auto x: C) {
//    cout << x << " ";
//  }
//  cout << "\n";

  FOR(i, 4, 32) {
    REP(j, 31) {
      if (j == pos || C[j]) {
        continue;
      }

      ans.push_back(R[i][j]);
    }
  }

  FOR(i, 33, sz(R) - 1) {
    REP(j, 31) {
      if (C[j]) {
        continue;
      }

      ans.push_back(R[i][j]);
    }
  }

  while (true) {
    int sv = ans.back();
    ans.pop_back();
    if (sv != ans.back()) {
      break;
    }
  }

//  for (auto x: ans) {
//    cout << x << " ";
//  }
//  cout << "\n";

  return ans;
}

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