Submission #1008745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008745		biank	Parrots (IOI11_parrots)	C++14	81 / 100	2739 ms	12828 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const int D = 512;
 
struct BigInt {
    bitset<D> num;
    BigInt(int x = 0) {
        for (int i = 0; i < 30; i++) {
            num[i] = x >> i & 1;
        }
    }
    int operator[](int i) { return num[i]; }
    friend BigInt operator+(BigInt x, BigInt y) {
        int carry = 0;
        BigInt z;
        for (int i = 0; i < D; i++) {
            int s = x[i] + y[i] + carry;
            carry = 0;
            while (s >= 2) s -= 2, carry++;
            z.num[i] = s;
        }
        return z;
    }
    friend BigInt operator-(BigInt x, BigInt y) {//x >= y
        int carry = 0;
        BigInt z;
        for (int i = 0; i < D; i++) {
            int s = x[i] - y[i] + carry;
            carry = 0;
            while (s < 0) s += 2, carry--;
            z.num[i] = s;
        }
        return z;
    }
    friend bool operator<(BigInt x, BigInt y) {
        for (int i = D - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return y[i];
        }
        return false;
    } 
    friend bool operator>=(BigInt x, BigInt y) {
        return !(x < y);
    }
    BigInt &operator+=(BigInt o) {
        return *this = *this + o;
    }
    BigInt &operator-=(BigInt o) {
        return *this = *this - o;
    }
    BigInt &operator<<=(int i) {
        num <<= i;
        return *this;
    }
    BigInt operator<<(int i) { return *this <<= i; }
};
 
const int MAXN = 350;
const int MAXA = 255;
 
BigInt dp[MAXN][MAXA];
bool flag = false;
 
void calcDP() {
    for (int i = 0; i < MAXA; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < MAXN; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < MAXA; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    flag = true;
}
 
void encode(int N, int M[]) {
    if (!flag) calcDP();
    BigInt pos = 0;
    for (int i = 0; i < N; i++) {
        pos = (pos << 8) + M[i];
    }
    pos += 1;
    for (int i = 5 * N - 1; i >= 0; i--) {
        int j = 0;
        while (pos >= dp[i][j]) {
            pos -= dp[i][j];
            j++;
        }
        //cerr << j << ' ';
        send(j);
    }
    //cerr << '\n';
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const int B = 512;
 
struct BigInt_de {
    bitset<B> num;
    BigInt_de(int x = 0) {
        for (int i = 0; i < 30; i++) {
            num[i] = x >> i & 1;
        }
    }
    int operator[](int i) { return num[i]; }
    friend BigInt_de operator+(BigInt_de x, BigInt_de y) {
        int carry = 0;
        BigInt_de z;
        for (int i = 0; i < B; i++) {
            int s = x[i] + y[i] + carry;
            carry = 0;
            while (s >= 2) s -= 2, carry++;
            z.num[i] = s;
        }
        return z;
    }
    friend BigInt_de operator-(BigInt_de x, BigInt_de y) {//x >= y
        int carry = 0;
        BigInt_de z;
        for (int i = 0; i < B; i++) {
            int s = x[i] - y[i] + carry;
            carry = 0;
            while (s < 0) s += 2, carry--;
            z.num[i] = s;
        }
        return z;
    }
    friend bool operator<(BigInt_de x, BigInt_de y) {
        for (int i = B - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return y[i];
        }
        return false;
    } 
    friend bool operator>=(BigInt_de x, BigInt_de y) {
        return !(x < y);
    }
    ll val() {
        return num.to_ulong();
    }
    BigInt_de &operator+=(BigInt_de o) {
        return *this = *this + o;
    }
    BigInt_de &operator-=(BigInt_de o) {
        return *this = *this - o;
    }
    BigInt_de operator&(BigInt_de o) {
        BigInt_de r;
        for (int i = 0; i < B; i++) r.num[i] = num[i] & o.num[i];
        return r;
    }
    BigInt_de &operator>>=(int i) {
        num >>= i;
        return *this;
    }
};
 
const int MAXN_DE = 350;
const int MAXA_DE = 255;
 
BigInt_de dp_de[MAXN_DE][MAXA_DE];
bool flag_de = false;
 
void calcDP_de() {
    for (int i = 0; i < MAXA_DE; i++) {
        dp_de[0][i] = 1;
    }
    for (int i = 1; i < MAXN_DE; i++) {
        dp_de[i][0] = dp_de[i - 1][0];
        for (int j = 1; j < MAXA_DE; j++) {
            dp_de[i][j] = dp_de[i - 1][j] + dp_de[i][j - 1];
        }
    }
    flag_de = true;
}
 
void decode(int N, int L, int X[]) {
    if (!flag_de) calcDP_de();
    sort(X, X + L);
    BigInt_de pos = 0;
    for (int i = L - 1; i >= 0; i--) {
        for (int j = 0; j < X[i]; j++) pos += dp_de[i][j];
    }
    pos -= 1;
    vector<int> res;
    for (int i = 0; i < N; i++) {
        BigInt_de x = pos & 255;
        res.push_back(x.val());
        pos >>= 8;
    }
    for (int i = N - 1; i >= 0; i--) {
        output(res[i]);
    }
}

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