oj.uz

Submission #1107987

# Submission time Handle Problem Language Result Execution time Memory
1107987 2024-11-02T14:19:14 Z sleepntsheep Message (IOI24_message) C++17
0 / 100
 1104 ms 656 KB 
#include "message.h"

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

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

    for (int i = 0; i < 66; ++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] = M[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 (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;
    for (int i = 0; i < 31; ++i) vis[i] = 0, gg[i].clear(), par[i] = 0, d[i] = 
1e9;
    for (int i = 0; i < 66; ++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]);

    std::vector<bool> M;

    for (int i = 0; i < 66; ++i)
	for (int j = 0; j < 16; ++j)
	    if (d[g[j]] < i + 1)
		    M.push_back(R[i][g[j]]);

    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:45:23: warning: unused variable 'S' [-Wunused-variable]
   45 |     int d[31], g[16], S = 0, z = 0;
      |                       ^
message.cpp:45:30: warning: unused variable 'z' [-Wunused-variable]
   45 |     int d[31], g[16], S = 0, z = 0;
      |                              ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 66 days

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1104 ms 408 KB Possible tampering with sol2mgr[1]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 66 days
2 Incorrect 1104 ms 408 KB Possible tampering with sol2mgr[1]
3 Halted 0 ms 0 KB -