Submission #285960

#	Time	Username	Problem	Language	Result	Execution time	Memory
285960		Kastanda	Parrots (IOI11_parrots)	C++14	99 / 100	598 ms	3824 KiB

encoder

// M
#include<bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
 
const int N = 256, MXN = N * 100, LIM = 7;
int ts1;
vector < int > TMp1, V1[MXN];
void Run1(int nw, int bt)
{
        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);
        sort(V1, V1 + ts1, [&](auto X, auto Y){return X.size() < Y.size();});
  		mt19937 Rnd(77);
  		shuffle(V1 + 1, V1 + N, Rnd);
}
 
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 = n - 1; i; 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, MXN = N * 100, LIM = 7;
int ts2;
vector < int > TMp2, V2[MXN];
map < vector < int > , int > MP;
void Run2(int nw, int bt)
{
        if (nw >= bt)
                return void(V2[ts2 ++] = TMp2);
        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);
        sort(V2, V2 + ts2, [&](auto X, auto Y){return X.size() < Y.size();});
  		mt19937 Rnd(77);
  		shuffle(V2 + 1, V2 + N, Rnd);
        for (int i = 0; i < N; i ++)
                MP[V2[i]] = i;
}
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 = 1; i < n; 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