oj.uz

Submission #1107984

# Submission time Handle Problem Language Result Execution time Memory
1107984 2024-11-02T14:11:33 Z sleepntsheep Message (IOI24_message) C++17
95 / 100
 1269 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() - 1) >> 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; ++S;

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

Compilation message

message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:79:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   79 |     for (int i = 0; i < 10; ++i) S |= buf[y++] << i; ++S;
      |     ^~~
message.cpp:79:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |     for (int i = 0; i < 10; ++i) S |= buf[y++] << i; ++S;
      |                                                      ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 916 KB Used 67 days

Subtask #1
9.5 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1196 ms 1016 KB Used 67 days
2 Partially correct 1159 ms 1152 KB Used 67 days
3 Partially correct 1198 ms 1148 KB Used 67 days
4 Partially correct 1141 ms 884 KB Used 67 days
5 Partially correct 824 ms 984 KB Used 67 days
6 Partially correct 617 ms 1000 KB Used 67 days
7 Partially correct 747 ms 1148 KB Used 67 days

Subtask #2
85.5 / 90.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 916 KB Used 67 days
2 Partially correct 1196 ms 1016 KB Used 67 days
3 Partially correct 1159 ms 1152 KB Used 67 days
4 Partially correct 1198 ms 1148 KB Used 67 days
5 Partially correct 1141 ms 884 KB Used 67 days
6 Partially correct 824 ms 984 KB Used 67 days
7 Partially correct 617 ms 1000 KB Used 67 days
8 Partially correct 747 ms 1148 KB Used 67 days
9 Partially correct 1184 ms 892 KB Used 67 days
10 Partially correct 1140 ms 892 KB Used 67 days
11 Partially correct 1168 ms 984 KB Used 67 days
12 Partially correct 1242 ms 892 KB Used 67 days
13 Partially correct 1218 ms 888 KB Used 67 days
14 Partially correct 845 ms 984 KB Used 67 days
15 Partially correct 648 ms 896 KB Used 67 days
16 Partially correct 875 ms 888 KB Used 67 days
17 Partially correct 870 ms 884 KB Used 67 days
18 Partially correct 1182 ms 1140 KB Used 67 days
19 Partially correct 1133 ms 1148 KB Used 67 days
20 Partially correct 1210 ms 892 KB Used 67 days
21 Partially correct 1203 ms 892 KB Used 67 days
22 Partially correct 1230 ms 888 KB Used 67 days
23 Partially correct 1186 ms 984 KB Used 67 days
24 Partially correct 1228 ms 1148 KB Used 67 days
25 Partially correct 1269 ms 988 KB Used 67 days
26 Partially correct 1228 ms 884 KB Used 67 days
27 Partially correct 1205 ms 1140 KB Used 67 days
28 Partially correct 1248 ms 988 KB Used 67 days