Submission #747170

#	Time	Username	Problem	Language	Result	Execution time	Memory
747170		finn__	Parrots (IOI11_parrots)	C++17	34 / 100	12 ms	19708 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <stdio.h>
#include <stdint.h>
#include <memory.h>
#include <stdbool.h>

typedef struct u512 u512;
struct u512
{
    uint64_t a[8];
};

inline void u512_add(u512 const *const x, u512 const *const y, u512 *const z)
{
    uint64_t carry = 0;
    for (size_t i = 0; i < 8; ++i)
    {
        z->a[i] = x->a[i] + y->a[i] + carry;
        carry = z->a[i] < x->a[i];
    }
}

inline void u512_subtract(u512 const *const x, u512 const *const y, u512 *const z)
{
    uint64_t carry = 0;
    for (size_t i = 0; i < 8; ++i)
    {
        z->a[i] = x->a[i] - y->a[i] - carry;
        carry = z->a[i] > x->a[i];
    }
}

inline bool u512_less(u512 const *const x, u512 const *const y)
{
    for (size_t i = 7; i < 8; --i)
        if (x->a[i] != y->a[i])
            return x->a[i] < y->a[i];
    return 0;
}

void u512_add(u512 const *const x, u512 const *const y, u512 *const z);
void u512_subtract(u512 const *const x, u512 const *const y, u512 *const z);
bool u512_less(u512 const *const x, u512 const *const y);

static u512 c[578][257];

inline void precalc_binomial_coefficient()
{
    c[0][0].a[0] = 1;
    for (size_t i = 1; i <= 577; ++i)
    {
        c[i][0].a[0] = 1;
        for (size_t j = 1; j <= 256; ++j)
            u512_add(c[i - 1] + j - 1, c[i - 1] + j, c[i] + j);
    }
}

void precalc_binomial_coefficient();

void encode(int n, int m[])
{
    if (!c[0][0].a[0])
        precalc_binomial_coefficient();
    u512 j;
    memset(j.a, 0, sizeof j.a);
    for (size_t i = 0; i < n; ++i)
        j.a[i >> 3] |= (uint64_t)m[i] << ((i & 7) << 3);

    size_t a = 0;
    for (size_t i = 0; i < 5 * n; ++i)
    {
        while (!u512_less(&j, c[5 * n - i - 1 + 256 - a] + 256 - a))
        {
            u512 k;
            u512_subtract(&j, c[5 * n - i - 1 + 256 - a] + 256 - a, &k);
            memcpy(j.a, k.a, sizeof j.a);
            ++a;
        }
        send(a);
    }
}

decoder

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

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>

typedef struct u512 u512;
struct u512
{
    uint64_t a[8];
};

inline void u512_add(u512 const *const x, u512 const *const y, u512 *const z)
{
    uint64_t carry = 0;
    for (size_t i = 0; i < 8; ++i)
    {
        z->a[i] = x->a[i] + y->a[i] + carry;
        carry = z->a[i] < x->a[i];
    }
}

u512 c_[578][257];

void precalc_binomial_coefficient_()
{
    c_[0][0].a[0] = 1;
    for (size_t i = 1; i <= 577; ++i)
    {
        c_[i][0].a[0] = 1;
        for (size_t j = 1; j <= 256; ++j)
            u512_add(c_[i - 1] + j - 1, c_[i - 1] + j, c_[i] + j);
    }
}

int compare_int(void const *const a, void const *const b)
{
    return *(int *)a - *(int *)b;
}

void decode(int n, int l, int x[])
{
    if (!c_[0][0].a[0])
        precalc_binomial_coefficient_();
    qsort(x, l, sizeof *x, compare_int);
    u512 j;
    memset(j.a, 0, sizeof j.a);

    size_t a = 0;
    for (size_t i = 0; i < 5 * n; ++i)
    {
        while (a < x[i])
        {
            u512 k;
            u512_add(&j, c_[5 * n - i - 1 + 256 - a] + 256 - a, &k);
            memcpy(j.a, k.a, sizeof j.a);
            ++a;
        }
    }

    for (size_t i = 0; i < n; ++i)
        output((j.a[i >> 3] >> ((i & 7) << 3)) & 255);
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:68:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
encoder.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t i = 0; i < 5 * n; ++i)
      |                        ~~^~~~~~~

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:53:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     for (size_t i = 0; i < 5 * n; ++i)
      |                        ~~^~~~~~~
decoder.cpp:55:18: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while (a < x[i])
      |                ~~^~~~~~
decoder.cpp:64:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~

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