Submission #561748

#	Time	Username	Problem	Language	Result	Execution time	Memory
561748		nghiass001	Parrots (IOI11_parrots)	C++17	100 / 100	69 ms	55972 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define getbit(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1 << (i))
using namespace std;

/// BigNum
const long long MOD = (long long)1e16;
typedef vector<long long> BigNum;

bool operator < (BigNum A, BigNum B) {
    if (A.size() != B.size()) return A.size() < B.size();
    REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i];
    return false;
}

bool operator <= (BigNum A, BigNum B) {
    if (A.size() != B.size()) return A.size() < B.size();
    REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i];
    return true;
}

BigNum operator + (BigNum A, BigNum B) {
    BigNum C(max(A.size(), B.size()));
    long long carry = 0;
    REP(i, 0, C.size()) {
        if (i < A.size()) carry += A[i];
        if (i < B.size()) carry += B[i];
        C[i] = carry % MOD;
        carry /= MOD;
    }
    if (carry) C.push_back(carry);
    return C;
}

BigNum operator + (BigNum A, int B) {
    return A + BigNum{B};
}

BigNum operator * (BigNum A, int B) {
    long long carry = 0;
    for(long long &v : A) {
        carry += v * B;
        v = carry % MOD;
        carry /= MOD;
    }
    if (carry) A.push_back(carry);
    return A;
}

BigNum operator / (BigNum A, int B) {
    long long carry = 0;
    REPD(i, (int)A.size(), 0) {
        carry = carry * MOD + A[i];
        A[i] = carry / B;
        carry %= B;
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
}

BigNum C[1000][1000];

BigNum getC(int n, int k) {
    if (C[n][k].size()) return C[n][k];
    if (k == 0) return C[n][k] = {1};
    if (k > n) return {};
    return C[n][k] = getC(n - 1, k) + getC(n - 1, k - 1);
}

void encode(int n, int a[]) {
    int c[n * 8], code[n * 5];
    int num = 0;
    REP(i, 0, n) {
        REP(j, 0, 8) {
            c[i * 8 + j] = getbit(a[i], j);
        }
    }

    int sz = n * 5;
    BigNum order = {1};
    REP(i, 0, n*8)
        order = order * 2 + c[i];

    auto get = [&](int n, int k) -> BigNum {/// x1 + x2 + ... + xk = n -> C(n + k - 1, k - 1)
        return getC(n + k - 1, k - 1);
    };

    int prv = 0;
    BigNum sum = {0};
    REP(i, 0, sz) {
        while (sum + get(sz - i - 1, 256 - prv) <= order) {
            sum = sum + get(sz - i - 1, 256 - prv);
            ++prv;
        }
        code[i] = prv;
    }

    REP(i, 0, sz) send(code[i]);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define getbit(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1 << (i))
using namespace std;

/// BigNum
const long long MOD = (long long)1e16;
typedef vector<long long> BigNum;

bool operator < (BigNum A, BigNum B) {
    if (A.size() != B.size()) return A.size() < B.size();
    REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i];
    return false;
}

bool operator <= (BigNum A, BigNum B) {
    if (A.size() != B.size()) return A.size() < B.size();
    REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i];
    return true;
}

BigNum operator + (BigNum A, BigNum B) {
    BigNum C(max(A.size(), B.size()));
    long long carry = 0;
    REP(i, 0, C.size()) {
        if (i < A.size()) carry += A[i];
        if (i < B.size()) carry += B[i];
        C[i] = carry % MOD;
        carry /= MOD;
    }
    if (carry) C.push_back(carry);
    return C;
}

BigNum operator + (BigNum A, int B) {
    return A + BigNum{B};
}

BigNum operator * (BigNum A, int B) {
    long long carry = 0;
    for(long long &v : A) {
        carry += v * B;
        v = carry % MOD;
        carry /= MOD;
    }
    if (carry) A.push_back(carry);
    return A;
}

BigNum operator / (BigNum A, int B) {
    long long carry = 0;
    REPD(i, (int)A.size(), 0) {
        carry = carry * MOD + A[i];
        A[i] = carry / B;
        carry %= B;
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
}

BigNum C[1000][1000];

BigNum getC(int n, int k) {
    if (C[n][k].size()) return C[n][k];
    if (k == 0) return C[n][k] = {1};
    if (k > n) return {};
    return C[n][k] = getC(n - 1, k) + getC(n - 1, k - 1);
}

void decode(int n, int sz, int b[]) {
    sort(b, b + sz);
    vector<int> a(n, 0);

    auto get = [&](int n, int k) -> BigNum {/// x1 + x2 + ... + xk = n -> C(n + k - 1, k - 1)
        return getC(n + k - 1, k - 1);
    };

    BigNum order = {0};
    int prv = 0;
    REP(i, 0, sz) {
        while (prv < b[i]) {
            order = order + get(sz - i - 1, 256 - prv);
            ++prv;
        }
    }
    REPD(i, n*8, 0) {
        if (order.size() && order[0] % 2 == 1) a[i / 8] += MASK(i % 8);
        order = order / 2;
    }

    REP(i, 0, n) output(a[i]);
}

Compilation message (stderr)

encoder.cpp: In function 'BigNum operator+(BigNum, BigNum)':
encoder.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
encoder.cpp:31:5: note: in expansion of macro 'REP'
   31 |     REP(i, 0, C.size()) {
      |     ^~~
encoder.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (i < A.size()) carry += A[i];
      |             ~~^~~~~~~~~~
encoder.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (i < B.size()) carry += B[i];
      |             ~~^~~~~~~~~~
encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:78:9: warning: unused variable 'num' [-Wunused-variable]
   78 |     int num = 0;
      |         ^~~

decoder.cpp: In function 'BigNum operator+(BigNum, BigNum)':
decoder.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
decoder.cpp:31:5: note: in expansion of macro 'REP'
   31 |     REP(i, 0, C.size()) {
      |     ^~~
decoder.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (i < A.size()) carry += A[i];
      |             ~~^~~~~~~~~~
decoder.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (i < B.size()) carry += B[i];
      |             ~~^~~~~~~~~~

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