Submission #99817

#	Time	Username	Problem	Language	Result	Execution time	Memory
99817		naoai	Parrots (IOI11_parrots)	C++14	100 / 100	1904 ms	13216 KiB

encoder

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

using namespace std;

const int nmax = 263;
const int ct = 256;
const int base = 1e9 / ct;

typedef vector<int> huge;
static huge p256[nmax + 1];
static huge d[nmax + 1][ct + 5];

static huge operator + (const huge &x, const huge &y) {
    int t = 0;
    huge z = x;

    for (int i = 0; i < y.size() || t > 0; ++ i) {
        if (i == z.size())
            z.push_back(0);

        t += z[i];
        if (i < y.size())
            t += y[i];

        if (t < base) {
            z[i] = t;
            t = 0;
        } else {
            z[i] = t - base;
            t = 1;
        }
    }
    return z;
}

static huge operator * (const huge &x, int y) {
    huge z = x;
    int t = 0;

    for (int i = 0; i < x.size() || t > 0; ++ i) {
        if (i == z.size())
            z.push_back(0);

        if (i < x.size())
            t += x[i] * y;

        z[i] = t % base;
        t /= base;
    }

    while (z.size() && z.back() == 0)
        z.pop_back();
    return z;
}

static bool operator < (const huge &x, const huge &y) {
    if (x.size() != y.size())
        return x.size() < y.size();

    for (int i = x.size() - 1; i >= 0; -- i)
        if (x[i] != y[i])
            return x[i] < y[i];
    return x[0] < y[0];
}

void encode(int N, int M[])
{
    for (int i = 0; i <= N; ++ i)
        p256[i].clear();

    p256[0].push_back(1);
    for (int i = 1; i <= N; ++ i)
        p256[i] = p256[i - 1] * ct;

    // al catelea e M printre alea de lg N?
    huge ind;
    ind.push_back(1);
    for (int i = 0; i < N; ++ i) {
        ind = ind + p256[N - i - 1] * M[i];
    }

    // d[i][j] = cate siruri crescatoare de 0..255 de lungime i exista, cu primul numar = j?
    for (int i = 0; i < ct; ++ i) {
        d[1][i] = vector<int> (1, 1);
    }

    for (int i = 2; i <= nmax; ++ i) {
        for (int j = ct - 1; j >= 0; -- j) {
            d[i][j] = d[i - 1][j] + d[i][j + 1];
        }
    }

    // care e al ind-ulea sir crescator
    // care e lungimea?
    int lungime = 0;
    huge cnt;
    while (1) {
        ++ lungime;
        huge aux = cnt;
        for (int i = 0; i < ct; ++ i) {
            aux = aux + d[lungime][i];
        }

        if (ind < aux || ind == aux) {
            break;
        }

        cnt = aux;
    }

    int lst = 0;
    for (int i = 1; i <= lungime; ++ i) {
        int rest = lungime - i + 1;
        for (int j = lst; j < ct; ++ j) {
            if (cnt + d[rest][j] < ind) {
                cnt = cnt + d[rest][j];
            } else {
                send(j);
                lst = j;
                break;
            }
        }
    }
}

decoder

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

using namespace std;

const int nmax = 263;
const int ct = 256;
const int base = 1e9 / ct;

typedef vector<int> huge;
static huge p256[nmax + 1];
static huge d[nmax + 1][ct + 1];

static huge operator + (const huge &x, const huge &y) {
    int t = 0;
    huge z = x;

    for (int i = 0; i < y.size() || t > 0; ++ i) {
        if (i == z.size())
            z.push_back(0);

        t += z[i];
        if (i < y.size())
            t += y[i];

        if (t < base) {
            z[i] = t;
            t = 0;
        } else {
            z[i] = t - base;
            t = 1;
        }
    }
    return z;
}

static huge operator * (const huge &x, int y) {
    huge z = x;
    int t = 0;

    for (int i = 0; i < x.size() || t > 0; ++ i) {
        if (i == z.size())
            z.push_back(0);

        if (i < x.size())
            t += x[i] * y;

        z[i] = t % base;
        t /= base;
    }
    while (z.size() && z.back() == 0)
        z.pop_back();
    return z;
}

static bool operator < (const huge &x, const huge &y) {
    if (x.size() != y.size())
        return x.size() < y.size();

    for (int i = x.size() - 1; i >= 0; -- i)
        if (x[i] != y[i])
            return x[i] < y[i];
    return x[0] < y[0];
}

void decode(int N, int L, int X[])
{
    sort(X, X + L);
    for (int i = 0; i < ct; ++ i) {
        d[1][i] = vector<int> (1, 1);
    }

    // d[i][j] = cate siruri crescatoare de 0..255 de lungime i exista, cu primul numar = j?
    for (int i = 2; i <= nmax; ++ i) {
        for (int j = ct - 1; j >= 0; -- j) {
            d[i][j] = d[i - 1][j] + d[i][j + 1];
        }
    }

    huge ind;
    ind.push_back(1);
    for (int i = 1; i < L; ++ i)
        for (int j = 0; j < ct; ++ j)
            ind = ind + d[i][j];

    int lst = 0;
    for (int i = 1; i <= L; ++ i) {
        for (int j = lst; j < X[i - 1]; ++ j)
            ind = ind + d[L - i + 1][j];
        lst = X[i - 1];
    }

    for (int i = 0; i <= N; ++ i)
        p256[i].clear();

    p256[0].push_back(1);
    for (int i = 1; i <= N; ++ i)
        p256[i] = p256[i - 1] * ct;

    // vreau al ind-ulea de lungime N
    huge total;
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < ct; ++ j) {
            if (total + p256[N - i - 1] < ind) {
                total = total + p256[N - i - 1];
            } else {
                output(j);
                break;
            }
        }
    }
}

Compilation message (stderr)

encoder.cpp: In function 'huge operator+(const huge&, const huge&)':
encoder.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < y.size() || t > 0; ++ i) {
                     ~~^~~~~~~~~~
encoder.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == z.size())
             ~~^~~~~~~~~~~
encoder.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < y.size())
             ~~^~~~~~~~~~
encoder.cpp: In function 'huge operator*(const huge&, int)':
encoder.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size() || t > 0; ++ i) {
                     ~~^~~~~~~~~~
encoder.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == z.size())
             ~~^~~~~~~~~~~
encoder.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < x.size())
             ~~^~~~~~~~~~

decoder.cpp: In function 'huge operator+(const huge&, const huge&)':
decoder.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < y.size() || t > 0; ++ i) {
                     ~~^~~~~~~~~~
decoder.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == z.size())
             ~~^~~~~~~~~~~
decoder.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < y.size())
             ~~^~~~~~~~~~
decoder.cpp: In function 'huge operator*(const huge&, int)':
decoder.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size() || t > 0; ++ i) {
                     ~~^~~~~~~~~~
decoder.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == z.size())
             ~~^~~~~~~~~~~
decoder.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < x.size())
             ~~^~~~~~~~~~

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