Submission #1107996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107996		sleepntsheep	Message (IOI24_message)	C++17	100 / 100	1218 ms	1248 KiB

message

    #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 < 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] = 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 < 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]);
     
        for (int i = 0; i < 66; ++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 (stderr)

message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:47:27: warning: unused variable 'S' [-Wunused-variable]
   47 |         int d[31], g[16], S = 0, z = 0, buf[20000], y = 0;
      |                           ^

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90