oj.uz

Submission #1105455

# Submission time Handle Problem Language Result Execution time Memory
1105455 2024-10-26T12:54:13 Z jerzyk Message (IOI24_message) C++17
87.1637 / 100
 1270 ms 1116 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 sum[40];
vector<bool> M;
int il = 0, cnt = 0;

inline int S(int a, int b)
{
    return sum[b + 1] - sum[a];
}

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;
    for(int i = 0; i < 36; ++i) sum[i] = 0;
    
    _M.pb(1);
    M = _M;
    vector<int> pos;
    vector<bool> bas(31, false);
    vector<vector<bool>> answer(100, bas);


    for(int i = 0; i < (int)C.size(); ++i)
    {
        sum[i + 1] = sum[i] + (int)(1 ^ C[i]);
        if(C[i] == 0)
            pos.pb(i);
    }
    int p = 0, k = 30;
    while(p + 1 < k)
    {
        //cerr << "BS1: " << p << " " << k << "\n";
        bool r = !(S(p, (p + k) / 2 - 1) >= (k - p + 2) / 4);
        if(p + 2 == k && C[p] == 0) r = 0;
        if(p + 2 == k && C[p] != 0) r = 1;
        for(int i = 0; i < (int)pos.size(); ++i)
        {
            if(pos[i] < p || pos[i] > k) answer[il][pos[i]] = Nxt();
            else answer[il][pos[i]] = r;
        }
        if(r)
            p = (p + k) / 2 + 1;
        else
            k = (p + k) / 2 - 1;
        ++il;
    }
    //cerr << "fp " << p << "\n";

    for(int i = 0; i < 30; ++i)
        if(i < p)
            answer[il + i][p] = C[i];
        else
            answer[il + i][p] = C[i + 1];
    
    for(int i = 0; i < 30; ++i)
        for(int j = 0; j < (int)pos.size(); ++j)
            if(pos[j] != p)
                answer[il + i][pos[j]] = Nxt();
    il += 29;
    while(cnt < (int)M.size())
    {
        ++il;
        for(int j = 0; j < (int)pos.size(); ++j)
            answer[il][pos[j]] = Nxt();
    }
    for(int i = 0; i <= il; ++i)
        send_packet(answer[i]);
    //cerr << "xd\n";
}

vector<bool> receive_message(vector<vector<bool>> R)
{
    il = 0; cnt = 0;
    int p = 0, k = 30;
    vector<int> pos;
    vector<pair<int, int>> ran;
    vector<bool> ans;
    while(p + 1 < k)
    {
        //cerr << "BS2: " << p << " " << k << "\n";
        ran.pb(make_pair(p, k));
        int bal = 0;
        for(int i = p; i <= k; ++i)
            bal += (int)R[il][i];
        if(bal < (k - p + 2) / 2)
            k = (p + k) / 2 - 1;
        else
            p = (p + k) / 2 + 1;
        ++il;
    }
    //cerr << "fp2 " << p << "\n";

    for(int i = 0; i < 30; ++i)
    {
        if(i == p) pos.pb(p);
        int dod = 0;
        if(i >= p) ++dod;
        if(R[il + i][p] == 0)
            pos.pb(i + dod);
    }
    if((int)pos.size() < 16) pos.pb(30);
    //cerr << "xd2\n";

    //cerr << R.size() << " Pos: \n";
    //for(int i = 0; i < (int)pos.size(); ++i)
        //cerr << pos[i] << " ";
    //cerr << "\n";

    for(int i = 0; i < il; ++i)
        for(int j = 0; j < (int)pos.size(); ++j)
            if(pos[j] < ran[i].st || pos[j] > ran[i].nd)
                ans.pb(R[i][pos[j]]);
    for(int i = 0; i < 30; ++i)
    {
        for(int j = 0; j < (int)pos.size(); ++j)
            if(pos[j] != p)
                ans.pb(R[il + i][pos[j]]);
    }
    il += 30;
    for(il = il; il < (int)R.size(); ++il)
        for(int j = 0; j < (int)pos.size(); ++j)
            ans.pb(R[il][pos[j]]);

    
    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 34 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 848 KB Used 34 days
2 Correct 650 ms 840 KB Used 34 days
3 Correct 659 ms 1100 KB Used 34 days
4 Correct 661 ms 1100 KB Used 34 days
5 Correct 467 ms 1108 KB Used 34 days
6 Correct 334 ms 844 KB Used 34 days
7 Correct 420 ms 856 KB Used 34 days

Subtask #2
77.16375 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Used 34 days
2 Correct 625 ms 848 KB Used 34 days
3 Correct 650 ms 840 KB Used 34 days
4 Correct 659 ms 1100 KB Used 34 days
5 Correct 661 ms 1100 KB Used 34 days
6 Correct 467 ms 1108 KB Used 34 days
7 Correct 334 ms 844 KB Used 34 days
8 Correct 420 ms 856 KB Used 34 days
9 Partially correct 1244 ms 1104 KB Used 69 days
10 Partially correct 807 ms 1108 KB Used 68 days
11 Partially correct 1242 ms 1108 KB Used 69 days
12 Partially correct 1270 ms 840 KB Used 68 days
13 Partially correct 1252 ms 1116 KB Used 68 days
14 Partially correct 893 ms 852 KB Used 69 days
15 Partially correct 649 ms 852 KB Used 69 days
16 Partially correct 908 ms 868 KB Used 69 days
17 Partially correct 928 ms 876 KB Used 68 days
18 Correct 637 ms 848 KB Used 34 days
19 Correct 646 ms 1104 KB Used 34 days
20 Correct 652 ms 1008 KB Used 34 days
21 Correct 671 ms 872 KB Used 34 days
22 Correct 651 ms 1108 KB Used 36 days
23 Correct 732 ms 852 KB Used 42 days
24 Correct 855 ms 864 KB Used 48 days
25 Correct 876 ms 852 KB Used 55 days
26 Correct 1051 ms 852 KB Used 61 days
27 Partially correct 1186 ms 884 KB Used 67 days
28 Partially correct 1211 ms 1108 KB Used 68 days