oj.uz

Submission #1107986

# Submission time Handle Problem Language Result Execution time Memory
1107986 2024-11-02T14:16:20 Z sleepntsheep Message (IOI24_message) C++17
95 / 100
 1256 ms 1148 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];

    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

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 / 0.0

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

Subtask #1
9.5 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1229 ms 984 KB Used 67 days
2 Partially correct 1209 ms 884 KB Used 67 days
3 Partially correct 1204 ms 892 KB Used 67 days
4 Partially correct 1194 ms 992 KB Used 67 days
5 Partially correct 847 ms 892 KB Used 67 days
6 Partially correct 648 ms 1144 KB Used 67 days
7 Partially correct 754 ms 1144 KB Used 67 days

Subtask #2
85.5 / 90.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 656 KB Used 67 days
2 Partially correct 1229 ms 984 KB Used 67 days
3 Partially correct 1209 ms 884 KB Used 67 days
4 Partially correct 1204 ms 892 KB Used 67 days
5 Partially correct 1194 ms 992 KB Used 67 days
6 Partially correct 847 ms 892 KB Used 67 days
7 Partially correct 648 ms 1144 KB Used 67 days
8 Partially correct 754 ms 1144 KB Used 67 days
9 Partially correct 1196 ms 1148 KB Used 67 days
10 Partially correct 1227 ms 992 KB Used 67 days
11 Partially correct 1251 ms 1144 KB Used 67 days
12 Partially correct 1226 ms 884 KB Used 67 days
13 Partially correct 1184 ms 980 KB Used 67 days
14 Partially correct 866 ms 904 KB Used 67 days
15 Partially correct 651 ms 992 KB Used 67 days
16 Partially correct 886 ms 1148 KB Used 67 days
17 Partially correct 874 ms 896 KB Used 67 days
18 Partially correct 1216 ms 988 KB Used 67 days
19 Partially correct 1173 ms 992 KB Used 67 days
20 Partially correct 1222 ms 892 KB Used 67 days
21 Partially correct 1233 ms 992 KB Used 67 days
22 Partially correct 1175 ms 988 KB Used 67 days
23 Partially correct 1214 ms 984 KB Used 67 days
24 Partially correct 1240 ms 1148 KB Used 67 days
25 Partially correct 1249 ms 896 KB Used 67 days
26 Partially correct 1182 ms 1144 KB Used 67 days
27 Partially correct 1200 ms 1144 KB Used 67 days
28 Partially correct 1256 ms 984 KB Used 67 days