oj.uz

Submission #1107963

# Submission time Handle Problem Language Result Execution time Memory
1107963 2024-11-02T13:07:11 Z sleepntsheep Message (IOI24_message) C++17
0 / 100
 1140 ms 416 KB 
#include "message.h"

void send_message(std::vector<bool> M, std::vector<bool> C) {
    int d[16] = { 0 }, g[16] = { 0 }, z = 0, buf[2000], 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] = 32 - g[15] + g[0];

    for (int i = 0; i < 10; ++i) buf[y++] = ((int)M.size() >> i) & 1;
    for (int x : M) buf[y++] = x;

    for (int i = 0; i < 67; ++i) {
	std::vector<bool> p(31);
	for (int k = 0, ii; k < 16; ++k) {
	    ii = g[k];
	    if (i + 1 == d[k])
		p[ii] = 1;
	    else if (i + 1 < d[k])
		p[ii] = 0;
	    else
		p[ii] = buf[z++];
	}
	send_packet(p);
    }
}

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 (!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] = { 0 }, g[16], e[31] = { 0 }, S = 0, z = 0, buf[2000];
    for (int i = 0; i < 31; ++i) vis[i] = 1, gg[i].clear();
    for (int i = 0; i < 67; ++i) {
	for (int j = 0; j < 31; ++j) {
	    if (!d[j] && R[i][j] == 1) {
		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;
    }

    for (int i = 0; i < 16; ++i) e[g[i]] = -1;

    for (int i = 0; i < 67; ++i) {
	for (int j = 0; j < 31; ++j) {
	    if (e[j] && d[j] <= i) {
		buf[z++] = R[i][j];
	    }
	}
    }

    for (int i = 0; i < 10; ++i) S |= buf[z++] << i;

    std::vector<bool> M;
    for (int i = 0; i < S; ++i) M.push_back(buf[z++]);
    return M;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB decoded message is incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1140 ms 416 KB decoded message is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB decoded message is incorrect
2 Halted 0 ms 0 KB -