Submission #764298

#	Time	Username	Problem	Language	Result	Execution time	Memory
764298		boris_mihov	Parrots (IOI11_parrots)	C++17	98 / 100	7 ms	1392 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <map>

const int MAXN = 64 + 6;
const int MAXNUM = 256 + 6;

struct State2
{
    int state[5];
    State2()
    {
        std::fill(state, state + 5, 0);
    }
};

int cnt2 = 0;
State2 convert[MAXNUM];
void brute(int left, int pos, State2 state)
{
    if (pos == 4)
    {
        if (cnt2 >= 256)
        {
            return;
        }
        
        state.state[pos] = left;
        convert[cnt2++] = state;
        return;
    }

    brute(left, pos + 1, state);
    if (left >= 1)
    {
        state.state[pos]++;
        brute(left - 1, pos, state);
    }
}

bool was2 = false;
void encode(int N, int M[])
{
    if (!was2)
    {
        State2 state;
        brute(7, 0, state);
    }

    for (int i = 0 ; i < N ; ++i)
    {
        for (int j = 0 ; j < 4 ; ++j)
        {
            for (int k = 0 ; k < convert[M[i]].state[j] ; ++k)
            {
                send(N * j + i);
            }
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <map>

const int MAXN = 64 + 6;

struct State
{
    int state[5];
    State()
    {
        std::fill(state, state + 5, 0);
    }

    friend bool operator < (const State &a, const State &b)
    {
        for (int i = 0 ; i < 5 ; ++i)
        {
            if (a.state[i] < b.state[i]) return true;
            if (a.state[i] > b.state[i]) return false;
        }

        return false;
    }
};

int cnt;
bool was = false;
std::map <State,int> mp;
void brute(int left, int pos, State state)
{
    if (pos == 4)
    {
        if (cnt >= 256)
        {
            return;
        }

        state.state[pos] = left;
        mp[state] = cnt++;
        return;
    }

    brute(left, pos + 1, state);
    if (left >= 1)
    {
        state.state[pos]++;
        brute(left - 1, pos, state);
    }
}

int ans[MAXN];
int lastBit[MAXN];

State a[MAXN];
void decode(int N, int L, int X[])
{
    if (!was)
    {
        cnt = 0;
        mp.clear();
        State state;
        brute(7, 0, state);
        was = true;
    }

    for (int i = 0 ; i < N ; ++i)
    {
        ans[i] = 0;
        for (int j = 0 ; j < 4 ; ++j)
        {
            a[i].state[j] = 0;
        }

        a[i].state[4] = 7;
    }

    for (int i = 0 ; i < L ; ++i)
    {
        a[X[i] % N].state[4]--;
        a[X[i] % N].state[X[i] / N]++;
    }

    for (int i = 0 ; i < N ; ++i)
    {
        output(mp[a[i]]);
    }
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 17 / 19