oj.uz

Submission #51373

# Submission time Handle Problem Language Result Execution time Memory
51373 2018-06-17T18:09:14 Z imeimi2000 Parrots (IOI11_parrots) C++17
100 / 100
 290 ms 112568 KB 
#include "encoder.h"
#include "encoderlib.h"

static const int mx = 256 + 320;

namespace enc {
    const int t = 80;
    struct bigint {
        int dat[t];
        bigint& operator+=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] += x.dat[i];
                if (i + 1 < t) {
                    dat[i + 1] += (dat[i] >> 8);
                    dat[i] &= 255;
                }
            }
            return *this;
        }
        bigint& operator-=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] -= x.dat[i];
                if (dat[i] < 0) {
                    if (i + 1 < t) --dat[i + 1];
                    dat[i] += 256;
                }
            }
            return *this;
        }
        bool operator<=(const bigint &x) const {
            for (int i = t; i--; ) {
                if (dat[i] < x.dat[i]) return 1;
                if (dat[i] > x.dat[i]) return 0;
            }
            return 1;
        }
    };
}

using namespace enc;

static bigint nCr[mx][mx];
static bool ch = 1;

static void wr() {
    nCr[0][0].dat[0] = 1;
    for (int i = 1; i < mx; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
}

static bigint& nHr(int n, int r) {
    return nCr[n + r - 1][r];
}

static int cnt[256];
void encode(int n, int msg[]) {
    if (ch) {
        ch = 0;
        wr();
    }
    for (int i = 0; i < 256; ++i) cnt[i] = 0;
    bigint m;
    for (int i = 0; i < n; ++i) {
        m.dat[i] = msg[i];
    }
    for (int i = n; i < t; ++i) {
        m.dat[i] = 0;
    }
    int c = 5 * n;
    for (int i = 0; i < 256; ++i) {
        while (nHr(256 - i, c) <= m) {
            m -= nHr(256 - i, c--);
            ++cnt[i];
        }
    }
    for (int i = 0; i < 256; ++i) {
        for (int j = 0; j < cnt[i]; ++j) {
            send(i);
        }
    }
}

#include "decoder.h"
#include "decoderlib.h"

static const int mx = 256 + 320;

namespace dec {
    const int t = 80;
    struct bigint {
        int dat[t];
        bigint& operator+=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] += x.dat[i];
                if (i + 1 < t) {
                    dat[i + 1] += (dat[i] >> 8);
                    dat[i] &= 255;
                }
            }
            return *this;
        }
        bigint& operator-=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] -= x.dat[i];
                if (dat[i] < 0) {
                    if (i + 1 < t) --dat[i + 1];
                    dat[i] += 256;
                }
            }
            return *this;
        }
        bool operator<=(const bigint &x) const {
            for (int i = t; i--; ) {
                if (dat[i] < x.dat[i]) return 1;
                if (dat[i] > x.dat[i]) return 0;
            }
            return 1;
        }
    };
}

using namespace dec;

static bigint nCr[mx][mx];
static bool ch = 1;

static void wr() {
    nCr[0][0].dat[0] = 1;
    for (int i = 1; i < mx; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
}

static bigint& nHr(int n, int r) {
    return nCr[n + r - 1][r];
}

static int cnt[256];

void decode(int n, int l, int x[]) {
    if (ch) {
        ch = 0;
        wr();
    }
    for (int i = 0; i < 256; ++i) cnt[i] = 0;
    bigint m;
    for (int i = 0; i < t; ++i) m.dat[i] = 0;
    int c = 5 * n - l;
    for (int i = 0; i < l; ++i) {
        ++cnt[x[i]];
    }
    for (int i = 256; i--; ) {
        while (cnt[i]--) {
            m += nHr(256 - i, ++c);
        }
    }
    for (int i = 0; i < n; ++i) {
        output(m.dat[i]);
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 110576 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 111328 KB Output is correct
2 Correct 237 ms 111464 KB Output is correct
3 Correct 246 ms 111696 KB Output is correct
4 Correct 279 ms 111696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 111696 KB Output is correct
2 Correct 256 ms 111696 KB Output is correct
3 Correct 235 ms 111760 KB Output is correct
4 Correct 230 ms 112072 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 112072 KB Output is correct
2 Correct 239 ms 112072 KB Output is correct
3 Correct 237 ms 112080 KB Output is correct
4 Correct 252 ms 112080 KB Output is correct
5 Correct 251 ms 112080 KB Output is correct
6 Correct 229 ms 112080 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 112112 KB Output is correct - P = 5.000000
2 Correct 245 ms 112112 KB Output is correct - P = 5.000000
3 Correct 238 ms 112112 KB Output is correct - P = 5.000000
4 Correct 239 ms 112288 KB Output is correct - P = 5.000000
5 Correct 290 ms 112568 KB Output is correct - P = 5.000000
6 Correct 254 ms 112568 KB Output is correct - P = 5.000000
7 Correct 243 ms 112568 KB Output is correct - P = 5.000000