Submission #1165600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165600		iah	Message (IOI24_message)	C++20	83.31 / 100	407 ms	860 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())

int cnt[2];
int f[36][36];

void pre_calc() {
  f[0][0] = 1;
  FOR(i, 0, 15) {
    FOR(j, 0, 15) {
      if (i == 0 && j == 0 || i + j > 30) {
        continue;
      }
      f[i][j] = 0;

      if (i > 0) {
        f[i][j] += f[i - 1][j];
      }

      if (j > 0) {
        f[i][j] += f[i][j - 1];
      }
    }
  }

//  cout << f[15][15] << "\n";
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
  pre_calc();
  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(j, 2) {
    cnt[j] = 0;
  }

  int lexico = 0;
  FORD(i, 30, 0) {
    if (id == i) {
      continue;
    }

    if (C[i]) {
      if (cnt[0] > 0) {
        lexico += f[cnt[0] - 1][cnt[1] + 1];
      }
    }

    cnt[C[i]] ++;
  }

  REP(i, 28) {
    vector < bool > packet(31, 0);
    REP(j, 31) {
      if (C[j]) {
        continue;
      }

      if (j == id) {
        packet[j] = bit(lexico, i);
        continue;
      }

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

    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);
  }

//  cout << lexico << "\n";
}

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";

  int lexico = 0;

  REP(i, 28) {
    if (R[i + 4][pos]) {
      lexico ^= mask(i);
    }
  }

  pre_calc();

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

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

    if (cnt[0] == 0) {
      C[j] = 1;
      cnt[1] --;
    }
    else if (lexico >= f[cnt[0] - 1][cnt[1]]) {
      lexico -= f[cnt[0] - 1][cnt[1]];
      cnt[1] --;
      C[j] = 1;
    }
    else {
      cnt[0] --;
    }

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

    i ++;
  }

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

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

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

  FOR(i, 32, 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