Submission #1224078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224078		nicolo_010	Message (IOI24_message)	C++20	83.31 / 100	411 ms	872 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
#define rep(i, k, n) for (int i =k; i < n; i++)
using ll = long long;
using pii = pair<int, int>;

void send_message(std::vector<bool> M, std::vector<bool> C) {
    v<int> bits;
    rep(i, 0, 31) {
      if (!C[i]) bits.push_back(i);
    }
    v<v<bool>> pack(5, v<bool>(31, false));
    rep(i, 0, 16) {
      int now = bits[(i+1)%16];
      int j = 0;
      //cout << i << endl;
      rep(j, 0, 5) {
        if (now&1) pack[j][bits[i]] = true;
        else pack[j][bits[i]] = false;
        now /= 2;
      }
    }
    rep(i, 0, 5) {
      send_packet(pack[i]);
    }
    //for (auto x : M) cout << x << " ";
    //cout << endl;
    v<bool> lg(31, false);
    int k = M.size();
    //cout << k << endl;
    rep(i, 0, 31) {
        if (C[i] == 1) continue;
        //cout << (k&1) << " " << k << endl;
        if (k&1) lg[i] = true;
        k /= 2;
    }
    send_packet(lg);
    int l = 0;
    rep(i, 0, (int)M.size()) {
        if (l == (int)M.size()) break;
        v<bool> A(31, false);
        rep(j, 0, 31) {
            if (l == (int)M.size()) break;
            if (C[j]) continue;
            A[j] = M[l];
            l++;
        }
        send_packet(A);
    }

}

v<int> par;
v<int> anterior;
v<int> vis;
v<int> cont;

void dfs(int n) {
    vis[n] = 1;
    //cout << n << endl;
    int u = par[n];
    if (vis[u] == 1) {
        anterior[u] = n;
        v<int> cycle;
        while (anterior[u] != par[n]) {
          cycle.push_back(anterior[u]);
          u = anterior[u];
        }
        cycle.push_back(par[n]);
        if ((int)cycle.size() == 16) {
          cont = cycle;
          vis[n] = 2;
          return;
        }
    }
    else if (vis[u] == 0) {
        anterior[u] = n;
        dfs(u);
    }
    vis[n] = 2;
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    par.resize(31);
    anterior.assign(31, -1);
    vis.assign(31, 0);
    cont.resize(6);
    v<bool> C(31, true);
    rep(i, 0, 31) {
        int n = 0;
        rep(j, 0, 5) {
          if (R[j][i] == 1) n += (1 << j);
        }
        par[i] = n;
    }   
    rep(i, 0, 31) {
      if (vis[i] == 0) dfs(i);
    } 
    for (auto x : cont) {
      //cout << x << endl;
      C[x] = false;
    }
    //for (auto x : C) cout << x << " "; cout << endl;
    int n = 0;
    int b = 0;
    //cout << endl;
    v<bool> aux = R[5];
    //for (auto x : aux) cout << x << " "; cout << endl;
    rep(i, 0, 31) {
      if (C[i]) continue;
      if (aux[i]) n += (1 << b);
      b++;
    }
    //cout << n << endl;
    //cout << n << endl;
    v<bool> message(n);
    int l = 0;
    rep(i, 6, (int)R.size()) {
        if (l == n) break;
        rep(j, 0, 31) {
            //cout << R[i][j] << " ";
            if (l == n) break;
            if (C[j]) continue;
            message[l] = R[i][j];
            l++;
        }
        //cout << endl;
    }
    return message;
}

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