Submission #285951

#	Time	Username	Problem	Language	Result	Execution time	Memory
285951		Kastanda	Parrots (IOI11_parrots)	C++11	99 / 100	14 ms	1792 KiB

encoder

// M
#include<bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;

const int N = 256, LIM = 7;
int ts1;
vector < int > TMp1, V1[N];
void Run1(int nw, int bt)
{
        if (ts1 >= N)
                return ;
        if (nw >= bt)
                return void(V1[ts1 ++] = TMp1);
        for (int i = 0; (int)TMp1.size() + i <= LIM; i ++)
        {
                for (int j = 0; j < i; j ++)
                        TMp1.push_back(nw);
                Run1(nw + 1, bt);
                for (int j = 0; j < i; j ++)
                        TMp1.pop_back();
        }
}
void Generate1(int lg)
{
        ts1 = 0;
        int bts = 8 - lg;
        int k = 1 << bts;

        Run1(0, k);
        assert(ts1 >= N);
}

void encode(int n, int B[])
{
        int lg = 6;
        if (n <= 32)
                lg = 5;

        vector < int > A(n);
        for (int i = 0; i < n; i ++)
                A[i] = B[i];

        Generate1(lg);

        for (int i = 1; i < n; i ++)
                A[i] = A[i] ^ A[i - 1];

        for (int i = 0; i < n; i ++)
                for (int a : V1[A[i]])
                        send((a << lg) | i);
}

decoder

// M
#include<bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;

const int N = 256, LIM = 7;
int ts2;
vector < int > TMp2;
map < vector < int > , int > MP;
void Run2(int nw, int bt)
{
        if (ts2 >= N)
                return ;
        if (nw >= bt)
                return void(MP[TMp2] = ts2 ++);
        for (int i = 0; (int)TMp2.size() + i <= LIM; i ++)
        {
                for (int j = 0; j < i; j ++)
                        TMp2.push_back(nw);
                Run2(nw + 1, bt);
                for (int j = 0; j < i; j ++)
                        TMp2.pop_back();
        }
}
void Generate2(int lg)
{
        ts2 = 0;
        int bts = 8 - lg;
        int k = 1 << bts;

        Run2(0, k);
        assert(ts2 >= N);
}
void decode(int n, int L, int X[])
{
        int lg = 6;
        if (n <= 32)
                lg = 5;

        Generate2(lg);

        vector < int > vec[64];
        for (int i = 0; i < L; i ++)
                vec[(X[i] & ((1 << lg) - 1))].push_back(X[i] >> lg);

        vector < int > A(n, 0);
        for (int i = 0; i < n; i ++)
        {
                sort(vec[i].begin(), vec[i].end());
                A[i] = MP[vec[i]];
        }

        for (int i = n - 1; i; i --)
                A[i] ^= A[i - 1];

        for (int i = 0; i < n; i ++)
                output(A[i]);
}

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