Submission #183103

#	Time	Username	Problem	Language	Result	Execution time	Memory
183103		tri	Parrots (IOI11_parrots)	C++14	98 / 100	13 ms	1776 KiB

encoder

#include <bits/stdc++.h>
#include "encoderlib.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int NTYPE = 5;
const int NSEND = 7;

array<int, NTYPE> cSeq;
vector<array<int, NTYPE>> seqs;

void enumerateCases(int i, int rem) {
    if (i == NTYPE - 1) {
        cSeq[i] = rem;
        seqs.push_back(cSeq);
        return;
    }

    for (int cSend = 0; cSend <= rem; cSend++) {
        cSeq[i] = cSend;
        enumerateCases(i + 1, rem - cSend);
    }
}

void send(int code, int times) {
    for (int i = 0; i < times; i++) {
        send(code);
    }
}

void encode(int N, int M[]) {
    if (seqs.empty()) {
        enumerateCases(0, NSEND);
    }
    assert(seqs.size() == 330);

    for (int i = 0; i < N; i++) {
        int prefix = i << 2;
        array<int, NTYPE> sSeq = seqs[M[i]];
        for (int cT = 0; cT < 4; cT++) {
            int cCode = prefix + cT;
            send(cCode, sSeq[cT]);
        }
    }
}

decoder

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int NTYPE = 5;
const int NSEND = 7;

array<int, NTYPE> cSeq1;
vector<array<int, NTYPE>> seqs1;

void enumerateCases1(int i, int rem) {
    if (i == NTYPE - 1) {
        cSeq1[i] = rem;
        seqs1.push_back(cSeq1);
        return;
    }

    for (int cSend = 0; cSend <= rem; cSend++) {
        cSeq1[i] = cSend;
        enumerateCases1(i + 1, rem - cSend);
    }
}

const int MAXN = 100;

array<int, 5> cnt[MAXN];

void decode(int N, int L, int X[]) {
    if (seqs1.empty()) {
        enumerateCases1(0, NSEND);
    }
    assert(seqs1.size() == 330);

    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i < L; i++) {
        int block = X[i] >> 2;
        int type = X[i] & 0b11;
        cnt[block][type]++;
    }

    for (int cB = 0; cB < N; cB++) {
        cnt[cB][4] = NSEND;

        for (int i = 0; i < 4; i++) {
            cnt[cB][4] -= cnt[cB][i];
        }

        array<int, NTYPE> key = cnt[cB];
        int val = lower_bound(seqs1.begin(), seqs1.end(), key) - seqs1.begin();
        output(val);
    }
}

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