oj.uz

Submission #561748

# Submission time Handle Problem Language Result Execution time Memory
561748 2022-05-13T12:34:41 Z nghiass001 Parrots (IOI11_parrots) C++17
100 / 100
 69 ms 55972 KB 
#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]);
}

#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

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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48256 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 48576 KB Output is correct
2 Correct 32 ms 48732 KB Output is correct
3 Correct 35 ms 49132 KB Output is correct
4 Correct 36 ms 49064 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48548 KB Output is correct
2 Correct 31 ms 48680 KB Output is correct
3 Correct 33 ms 49068 KB Output is correct
4 Correct 33 ms 49104 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48708 KB Output is correct
2 Correct 35 ms 49052 KB Output is correct
3 Correct 41 ms 49500 KB Output is correct
4 Correct 44 ms 50388 KB Output is correct
5 Correct 41 ms 50512 KB Output is correct
6 Correct 42 ms 50752 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49156 KB Output is correct - P = 5.000000
2 Correct 53 ms 50612 KB Output is correct - P = 5.000000
3 Correct 44 ms 50764 KB Output is correct - P = 5.000000
4 Correct 53 ms 53292 KB Output is correct - P = 5.000000
5 Correct 68 ms 55092 KB Output is correct - P = 5.000000
6 Correct 65 ms 55944 KB Output is correct - P = 5.000000
7 Correct 69 ms 55972 KB Output is correct - P = 5.000000