oj.uz

Submission #100580

# Submission time Handle Problem Language Result Execution time Memory
100580 2019-03-12T13:59:22 Z alexpetrescu Parrots (IOI11_parrots) C++14
100 / 100
 532 ms 11248 KB 
#include "encoder.h"
#include "encoderlib.h"
//#include <cstdio>
#include <vector>

#define vec std::vector
#define ll long long

const ll MASK = (1LL << 56) - 1;

inline void aranjez(vec < ll > &a) {
    while (!a.empty() && a.back() == 0)
        a.pop_back();
}

inline void scad(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        tr += a[i];
        if (i < (int)b.size())
            tr -= b[i];
        if (tr < 0) {
            a[i] = (tr + MASK + 1) & MASK;
            tr = -1;
        } else {
            a[i] = tr;
            tr = 0;
        }
    }
    aranjez(a);
}

inline void adun(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        if (i < (int)b.size())
            tr += b[i];
        if (i < (int)a.size()) {
            tr += a[i];
            a[i] = tr & MASK;
            tr >>= 56;
        } else {
            a.push_back(tr & MASK);
            tr >>= 56;
        }
    }
}

inline bool cmp(vec < ll > &a, vec < ll > &b) {
    if (a.size() != b.size())
        return a.size() < b.size();
    int poz = a.size() - 1;
    while (poz >= 0 && a[poz] == b[poz])
        poz--;
    if (poz >= 0)
        return a[poz] < b[poz];
    else
        return 0;
}

void encode(int N, int M[]) {
    vec < ll > val;
    for (int i = N - 1; i >= 0; i -= 7) {
        ll r = M[i];
        for (int j = 1; j < 7 && i - j >= 0; j++)
            r |= (1LL * M[i - j]) << (8 * j);
        val.push_back(r);
    }
    aranjez(val);
    if (val.empty())
        return ;

    vec < ll > unu(1, 1), sum(1, 256);
    vec < vec < ll > > lin(256, unu);
    vec < vec < vec < ll > > > dp(1, lin);
    int n = 1;
    while (cmp(sum, val)) {
        n++;
        scad(val, sum);
        sum.clear();
        for (int j = 254; j >= 0; j--)
            adun(lin[j], lin[j + 1]);
        for (int j = 0; j < 256; j++)
            adun(sum, lin[j]);
        dp.push_back(lin);
    }
    //printf("\n%f\n\n", n / (double) N);

    int cat = 0;
    for (int i = 1; i <= n; i++) {
        while (cmp(dp[n - i][cat], val)) {
            scad(val, dp[n - i][cat]);
            cat++;
        }
        send(cat);
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <vector>

#define vec std::vector
#define ll long long

const ll MASK = (1LL << 56) - 1;

inline void adun(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        if (i < (int)b.size())
            tr += b[i];
        if (i < (int)a.size()) {
            tr += a[i];
            a[i] = tr & MASK;
            tr >>= 56;
        } else {
            a.push_back(tr & MASK);
            tr >>= 56;
        }
    }
}

void decode(int N, int L, int X[]) {
    if (L == 0) {
        for (int i = 0; i < N; i++)
            output(0);
        return ;
    }
    std::sort(X, X + L);

    /*printf("I received %d element(s): ", L);
    for (int i = 0; i < L; i++)
        printf("%d ", X[i]);
    printf("\n\n");*/

    vec < ll > sum(1, 1), unu(1, 1);
    vec < vec < ll > > lin(256, unu);
    vec < vec < vec < ll > > > dp(1, lin);
    int n = 1;
    while (n < L) {
        for (int i = 0; i < 256; i++)
            adun(sum, lin[i]);
        for (int j = 254; j >= 0; j--)
            adun(lin[j], lin[j + 1]);
        dp.push_back(lin);
        n++;
    }

    int cat = 0;
    for (int i = 1; i <= n; i++) {
        while (cat < X[i - 1]) {
            adun(sum, dp[n - i][cat]);
            cat++;
        }
    }

    std::vector < int > ans(N, 0);
    int poz = 0, mask = (1 << 8) - 1;
    for (int i = N - 1; i >= 0; i -= 7) {
        ll x = 0;
        if (poz < (int)sum.size())
            x = sum[poz];
        poz++;
        ans[i] = x & mask;
        for (int j = 1; j < 7 && i - j >= 0; j++) {
            x >>= 8;
            ans[i - j] = x & mask;
        }
    }

    for (int i = 0; i < N; i++)
        output(ans[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1052 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1792 KB Output is correct
2 Correct 33 ms 1824 KB Output is correct
3 Correct 46 ms 2304 KB Output is correct
4 Correct 53 ms 2288 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1792 KB Output is correct
2 Correct 32 ms 2048 KB Output is correct
3 Correct 45 ms 2304 KB Output is correct
4 Correct 59 ms 2288 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1856 KB Output is correct
2 Correct 52 ms 2288 KB Output is correct
3 Correct 72 ms 2800 KB Output is correct
4 Correct 136 ms 3824 KB Output is correct
5 Correct 134 ms 3832 KB Output is correct
6 Correct 136 ms 3824 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2304 KB Output is correct - P = 1.750000
2 Correct 156 ms 3936 KB Output is correct - P = 2.437500
3 Correct 150 ms 4080 KB Output is correct - P = 2.484848
4 Correct 409 ms 7160 KB Output is correct - P = 3.280000
5 Correct 476 ms 9968 KB Output is correct - P = 3.833333
6 Correct 532 ms 11016 KB Output is correct - P = 4.015873
7 Correct 508 ms 11248 KB Output is correct - P = 4.078125