oj.uz

Submission #1100044

# Submission time Handle Problem Language Result Execution time Memory
1100044 2024-10-12T15:07:54 Z fve5 Message (IOI24_message) C++17
100 / 100
 1025 ms 1056 KB 
#include <bits/stdc++.h>
#include "message.h"
using namespace std;

constexpr int MAXS = 1024;
constexpr int SIZE = 31;
constexpr int PACKETS = 66;
constexpr int GOOD_BITS = 16;

void send_message(vector<bool> M, vector<bool> C) {
    M.push_back(1);
    while (M.size() <= MAXS)
        M.push_back(0);
    
    vector<int> nxt(SIZE);
    for (int i = 0; i < SIZE; i++) {
        while (C[(i + nxt[i] + 1) % SIZE])
            nxt[i]++;
    }

    int idx = 0;
    for (int i = 0; i < PACKETS; i++) {
        vector<bool> packet(SIZE);
        for (int j = 0; j < SIZE; j++) {
            if (C[j])
                continue;
            
            if (i < nxt[j])
                packet[j] = 1;
            else if (i == nxt[j])
                packet[j] = 0;
            else
                packet[j] = M[idx++];
        }

        send_packet(packet);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    vector<int> nxt(SIZE), true_nxt(SIZE);
    for (int i = 0; i < SIZE; i++) {
        while (nxt[i] < GOOD_BITS - 1 && R[nxt[i]][i])
            nxt[i]++;
        true_nxt[i] = (i + nxt[i] + 1) % SIZE;
    }

    vector<int> good_bits;

    for (int i = 0; i < SIZE; i++) {
        vector<bool> vis(SIZE);
        deque<int> cycle;
        
        int curr;
        for (curr = i; !vis[curr]; curr = true_nxt[curr]) {
            vis[curr] = true;
            cycle.push_back(curr);
        }

        while (cycle.front() != curr)
            cycle.pop_front();
        
        if (cycle.size() == GOOD_BITS)
            good_bits = vector(cycle.begin(), cycle.end());
    }

    sort(good_bits.begin(), good_bits.end());
    
    vector<bool> message;
    for (int i = 0; i < PACKETS; i++)
        for (auto j: good_bits)
            if (i > nxt[j])
                message.push_back(R[i][j]);
    
    while (!message.back())
        message.pop_back();
    message.pop_back();
    return message;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 824 KB Used 66 days
2 Correct 898 ms 796 KB Used 66 days
3 Correct 857 ms 1052 KB Used 66 days
4 Correct 877 ms 800 KB Used 66 days
5 Correct 661 ms 804 KB Used 66 days
6 Correct 508 ms 820 KB Used 66 days
7 Correct 573 ms 800 KB Used 66 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 920 KB Used 66 days
2 Correct 930 ms 824 KB Used 66 days
3 Correct 898 ms 796 KB Used 66 days
4 Correct 857 ms 1052 KB Used 66 days
5 Correct 877 ms 800 KB Used 66 days
6 Correct 661 ms 804 KB Used 66 days
7 Correct 508 ms 820 KB Used 66 days
8 Correct 573 ms 800 KB Used 66 days
9 Correct 897 ms 1056 KB Used 66 days
10 Correct 949 ms 1004 KB Used 66 days
11 Correct 913 ms 1052 KB Used 66 days
12 Correct 885 ms 804 KB Used 66 days
13 Correct 889 ms 800 KB Used 66 days
14 Correct 675 ms 792 KB Used 66 days
15 Correct 519 ms 816 KB Used 66 days
16 Correct 670 ms 1056 KB Used 66 days
17 Correct 661 ms 1056 KB Used 66 days
18 Correct 892 ms 1056 KB Used 66 days
19 Correct 953 ms 820 KB Used 66 days
20 Correct 1025 ms 804 KB Used 66 days
21 Correct 927 ms 792 KB Used 66 days
22 Correct 978 ms 796 KB Used 66 days
23 Correct 842 ms 792 KB Used 66 days
24 Correct 875 ms 796 KB Used 66 days
25 Correct 912 ms 812 KB Used 66 days
26 Correct 968 ms 800 KB Used 66 days
27 Correct 944 ms 1048 KB Used 66 days
28 Correct 896 ms 1052 KB Used 66 days