oj.uz

Submission #1107982

# Submission time Handle Problem Language Result Execution time Memory
1107982 2024-11-02T14:10:32 Z sleepntsheep Message (IOI24_message) C++17
9.5 / 100
 1191 ms 1152 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[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];

    for (int i = 0; i < 10; ++i) buf[y++] = ((int)M.size() >> i) & 1;
    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]];
	    }
	}
    }

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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 744 KB Used 67 days

Subtask #1
9.5 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1188 ms 896 KB Used 67 days
2 Partially correct 1181 ms 888 KB Used 67 days
3 Partially correct 1174 ms 900 KB Used 67 days
4 Partially correct 1191 ms 896 KB Used 67 days
5 Partially correct 893 ms 1148 KB Used 67 days
6 Partially correct 645 ms 884 KB Used 67 days
7 Partially correct 750 ms 1152 KB Used 67 days

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 744 KB Used 67 days
2 Partially correct 1188 ms 896 KB Used 67 days
3 Partially correct 1181 ms 888 KB Used 67 days
4 Partially correct 1174 ms 900 KB Used 67 days
5 Partially correct 1191 ms 896 KB Used 67 days
6 Partially correct 893 ms 1148 KB Used 67 days
7 Partially correct 645 ms 884 KB Used 67 days
8 Partially correct 750 ms 1152 KB Used 67 days
9 Incorrect 1156 ms 492 KB decoded message is incorrect
10 Halted 0 ms 0 KB -