Submission #1105455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105455		jerzyk	Message (IOI24_message)	C++17	87.16 / 100	1270 ms	1116 KiB

message

#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
• Subtask 1: 10 / 10
• Subtask 2: 77.16375 / 90