oj.uz

Submission #1106303

# Submission time Handle Problem Language Result Execution time Memory
1106303 2024-10-29T19:28:28 Z jerzyk Message (IOI24_message) C++17
100 / 100
 1173 ms 1108 KB 
#include <bits/stdc++.h>
#include "message.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;
int xddd[40];
int jp[40];
vector<bool> M;
int il = 0, cnt = 0;

bool Nxt()
{
    if(cnt >= (int)M.size()) return 0;
    return M[cnt++];
}

void send_message(vector<bool> _M, vector<bool> C)
{
    il = 0; cnt = 0;
    
    M.clear();
    _M.pb(1);
    M = _M;
    vector<int> pos, dis;
    vector<bool> bas(31, false);
    vector<vector<bool>> answer(100, bas);

    for(int i = 0; i < (int)C.size(); ++i)
        if(C[i] == 0)
            pos.pb(i);
    for(int i = 0; i < 16; ++i)
    {
        int d;
        if(i < 15)
            d = pos[i + 1] - pos[i];
        else
            d = 31 + pos[0] - pos[i];
        dis.pb(d);
        answer[d - 1][pos[i]] = true;
        il = max(il, d - 1);
    }
    for(int l = 0; cnt < (int)M.size(); ++l)
    {
        il = max(il, l);
        for(int i = 0; i < 16; ++i)
            if(dis[i] < l + 1)
                answer[l][pos[i]] = Nxt();
    }
    while((int)answer.size() > il + 1)
        answer.pop_back();
    for(int i = 0; i < (int)answer.size(); ++i)
        send_packet(answer[i]);
}

vector<bool> receive_message(vector<vector<bool>> R)
{
    il = 0; cnt = 0;
    vector<int> pos, dis;
    vector<bool> ans;
    for(int i = 1; i < 35; ++i)
    {
        jp[i] = 0; xddd[i] = 0;
    }
    for(int i = 0; i < 31; ++i)
    {
        int d = 1, l = 0;
        while(l < (int)R.size() && R[l][i] != 1)
            {++l; ++d;}
        xddd[i] = d;
        jp[i] = (i + d) % 31;
    }
    for(int i = 0; i < 31; ++i)
    {
        int d = 1, v = jp[i];
        while(v != i && d < 17)
        {
            ++d;
            v = jp[v];
        }
        if(d == 16)
        {
            dis.pb(xddd[i]);
            pos.pb(i);
        }
    }
    for(int l = 0; l < (int)R.size(); ++l)
        for(int i = 0; i < (int)pos.size(); ++i)
            if(dis[i] < l + 1)
                ans.pb(R[l][pos[i]]);
    while(ans.back() == 0)
        ans.pop_back();
    ans.pop_back();
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 844 KB Used 9 days
2 Correct 162 ms 848 KB Used 12 days
3 Correct 159 ms 1104 KB Used 8 days
4 Correct 149 ms 1100 KB Used 9 days
5 Correct 165 ms 856 KB Used 16 days
6 Correct 142 ms 1108 KB Used 16 days
7 Correct 93 ms 856 KB Used 8 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 16 days
2 Correct 159 ms 844 KB Used 9 days
3 Correct 162 ms 848 KB Used 12 days
4 Correct 159 ms 1104 KB Used 8 days
5 Correct 149 ms 1100 KB Used 9 days
6 Correct 165 ms 856 KB Used 16 days
7 Correct 142 ms 1108 KB Used 16 days
8 Correct 93 ms 856 KB Used 8 days
9 Correct 1155 ms 848 KB Used 66 days
10 Correct 652 ms 896 KB Used 66 days
11 Correct 1146 ms 1108 KB Used 66 days
12 Correct 1173 ms 868 KB Used 66 days
13 Correct 1157 ms 848 KB Used 65 days
14 Correct 842 ms 864 KB Used 66 days
15 Correct 618 ms 864 KB Used 66 days
16 Correct 841 ms 1100 KB Used 66 days
17 Correct 848 ms 848 KB Used 66 days
18 Correct 160 ms 1100 KB Used 9 days
19 Correct 261 ms 864 KB Used 15 days
20 Correct 367 ms 1100 KB Used 21 days
21 Correct 462 ms 1104 KB Used 27 days
22 Correct 562 ms 856 KB Used 34 days
23 Correct 642 ms 1096 KB Used 40 days
24 Correct 792 ms 1100 KB Used 46 days
25 Correct 907 ms 1100 KB Used 52 days
26 Correct 1004 ms 844 KB Used 59 days
27 Correct 1097 ms 868 KB Used 65 days
28 Correct 1090 ms 1104 KB Used 66 days