oj.uz

Submission #99817

# Submission time Handle Problem Language Result Execution time Memory
99817 2019-03-07T15:46:47 Z naoai Parrots (IOI11_parrots) C++14
100 / 100
 1904 ms 13216 KB 
#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;
            }
        }
    }
}

#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12016 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 12920 KB Output is correct
2 Correct 839 ms 12784 KB Output is correct
3 Correct 1020 ms 12728 KB Output is correct
4 Correct 901 ms 12808 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 12544 KB Output is correct
2 Correct 961 ms 12784 KB Output is correct
3 Correct 925 ms 12784 KB Output is correct
4 Correct 956 ms 12760 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 12272 KB Output is correct
2 Correct 1011 ms 12528 KB Output is correct
3 Correct 1042 ms 12488 KB Output is correct
4 Correct 1110 ms 12800 KB Output is correct
5 Correct 1075 ms 12784 KB Output is correct
6 Correct 1034 ms 12784 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 12312 KB Output is correct - P = 1.750000
2 Correct 1077 ms 12864 KB Output is correct - P = 2.437500
3 Correct 1121 ms 12912 KB Output is correct - P = 2.484848
4 Correct 1419 ms 12784 KB Output is correct - P = 3.280000
5 Correct 1861 ms 12920 KB Output is correct - P = 3.833333
6 Correct 1904 ms 13216 KB Output is correct - P = 4.015873
7 Correct 1874 ms 12784 KB Output is correct - P = 4.078125