oj.uz

Submission #1107996

# Submission time Handle Problem Language Result Execution time Memory
1107996 2024-11-02T14:29:29 Z sleepntsheep Message (IOI24_message) C++17
100 / 100
 1218 ms 1248 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 < 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

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 892 KB Used 66 days
2 Correct 1174 ms 988 KB Used 66 days
3 Correct 1196 ms 988 KB Used 66 days
4 Correct 1214 ms 984 KB Used 66 days
5 Correct 881 ms 1144 KB Used 66 days
6 Correct 610 ms 984 KB Used 66 days
7 Correct 718 ms 1144 KB Used 66 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 66 days
2 Correct 1171 ms 892 KB Used 66 days
3 Correct 1174 ms 988 KB Used 66 days
4 Correct 1196 ms 988 KB Used 66 days
5 Correct 1214 ms 984 KB Used 66 days
6 Correct 881 ms 1144 KB Used 66 days
7 Correct 610 ms 984 KB Used 66 days
8 Correct 718 ms 1144 KB Used 66 days
9 Correct 1168 ms 896 KB Used 66 days
10 Correct 1165 ms 1248 KB Used 66 days
11 Correct 1141 ms 1144 KB Used 66 days
12 Correct 1183 ms 888 KB Used 66 days
13 Correct 1164 ms 884 KB Used 66 days
14 Correct 850 ms 888 KB Used 66 days
15 Correct 626 ms 1152 KB Used 66 days
16 Correct 870 ms 988 KB Used 66 days
17 Correct 872 ms 988 KB Used 66 days
18 Correct 1115 ms 892 KB Used 66 days
19 Correct 1153 ms 1148 KB Used 66 days
20 Correct 1188 ms 988 KB Used 66 days
21 Correct 1174 ms 896 KB Used 66 days
22 Correct 1198 ms 1152 KB Used 66 days
23 Correct 1162 ms 888 KB Used 66 days
24 Correct 1112 ms 892 KB Used 66 days
25 Correct 1218 ms 984 KB Used 66 days
26 Correct 1198 ms 992 KB Used 66 days
27 Correct 1213 ms 984 KB Used 66 days
28 Correct 1162 ms 1148 KB Used 66 days