Submission #1107986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107986		sleepntsheep	Message (IOI24_message)	C++17	95 / 100	1256 ms	1148 KiB

message

#include "message.h"

void send_message(std::vector<bool> M, std::vector<bool> C) {
    int d[16] = { 0 }, g[16] = { 0 }, z = 0, buf[20000], y = 0;
    for (int j = 0, i = 0; i < 31; ++i) if (!C[i]) g[j++] = i;
    for (int i = 0; i < 15; ++i) d[i] = g[i + 1] - g[i];
    d[15] = 31 - g[15] + g[0];

    M.push_back(1);
    while (M.size() < 1025) M.push_back(0);

    for (bool x : M) buf[y++] = x;
    for (int i = 0; i < 67; ++i) {
	std::vector<bool> p(31, false);
	for (int k = 0, ii; k < 16; ++k) {
	    ii = g[k];
	    if (i + 1 == d[k])
		p[ii] = true;
	    else if (i + 1 < d[k])
		p[ii] = false;
	    else
		p[ii] = buf[z++];
	}
	send_packet(p);
    }
}
#include<stdio.h>

std::vector<int> gg[31];
int head, tail, par[31], vis[31];

int cycle(int u, int p) {
    vis[u] = 1;
    par[u] = p;
    for (int v : gg[u]) if (v != p) {
	if (!vis[v]) {
	    if (cycle(v, u)) return 1;
	} else {
	    head = u; tail = v;
	    return 1;
	}
    }
    return 0;
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    int d[31], g[16], S = 0, z = 0, buf[20000], y = 0;
    for (int i = 0; i < 31; ++i) vis[i] = 0, gg[i].clear(), par[i] = 0, d[i] = 
1e9;
    for (int i = 0; i < 67; ++i) {
	for (int j = 0; j < 31; ++j) {
	    if (1e9 == d[j] && R[i][j]) {
		d[j] = (j + i + 1) % 31;
		gg[j].push_back(d[j]);
		gg[d[j]].push_back(j);
	    }
	}
    }

    for (int i = 0, p = 0; i < 31; ++i) if (!vis[i] && cycle(i, i)) {
	for (int c = head; c != tail; c = par[c]) g[p++] = c;
	g[p++] = tail;
	if (p == 16) break;
	p = 0;
    }

    for (int i = 0; i < 16; ++i) for (int j = 0, t; j < 15; ++j) 
if(g[j] > g[j + 1]) t = g[j], g[j] = g[j + 1], g[j + 1] = t;

    for (int i = 0; i < 16; ++i) d[g[i]] = (i == 15) ? (*g + 31 - 
g[i]) : (g[i + 1] - g[i]);

    for (int i = 0; i < 67; ++i) {
	for (int j = 0; j < 16; ++j) {
	    if (d[g[j]] < i + 1) {
		buf[z++] = R[i][g[j]];
	    }
	}
    }

    std::vector<bool> M;
    for (int i = 0; i < 1025; ++i) M.push_back(buf[y++]);
    while (M.back() == 0) M.pop_back();
    M.pop_back();
    return M;
}

Compilation message (stderr)

message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:47:23: warning: unused variable 'S' [-Wunused-variable]
   47 |     int d[31], g[16], S = 0, z = 0, buf[20000], y = 0;
      |                       ^

• Subtask 0: 0 / 0
• Subtask 1: 9.5 / 10
• Subtask 2: 85.5 / 90