Submission #370862

#	Time	Username	Problem	Language	Result	Execution time	Memory
370862		Sorting	Parrots (IOI11_parrots)	C++17	100 / 100	278 ms	211596 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int H = 320 + 256 + 3;
const int SZ = 80;

struct Big_Number{
    int a[SZ];

    void init(){ fill(a, a + SZ, 0); }
    Big_Number(){ init(); }

    friend Big_Number operator+(const Big_Number &l, const Big_Number &r){
        int add = 0;
        Big_Number ret;
        for(int i = SZ - 1; i >= 0; --i){
            int sum = l.a[i] + r.a[i] + add;
            ret.a[i] = sum % 256;
            add = sum / 256;
        }
        return ret;
    }

    friend bool operator<(const Big_Number &l, const Big_Number &r){
        for(int i = 0; i < SZ; ++i)
            if(l.a[i] != r.a[i])
                return l.a[i] < r.a[i];
        return false;
    }
};

static bool done = false;
static Big_Number bc[H][H];

static void output_number(Big_Number bn){
    bool start = false;
    for(int i = 0; i < SZ; ++i){
        if(bn.a[i]) start = true;
        if(start) cout << bn.a[i] << " ";
    }
    cout << endl;
}

void encode(int n, int m[]){
    if(!done){
        bc[0][0].a[SZ - 1] = 1;
        for(int i = 0; i < H; ++i){
            bc[i][0].a[SZ - 1] = 1;
            for(int j = 1; j <= i; ++j)
                bc[i][j] = bc[i - 1][j] + bc[i - 1][j - 1];
        }
        done = true;
    }

    int t = 5 * n, num = 255;
    Big_Number curr, add;
    for(int i = 0; i < n; ++i)
        curr.a[SZ - 1 - i] = m[i];
    for(; t > 0; --t){
        while(num && curr < bc[t + num - 1][t] + add) num--;
        send(num);
        add = add + bc[t + num - 1][t];
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int H = 320 + 256 + 3;
const int SZ = 80;

struct Big_Number{
    int a[SZ];

    void init(){ fill(a, a + SZ, 0); }
    Big_Number(){ init(); }

    friend Big_Number operator+(const Big_Number &l, const Big_Number &r){
        int add = 0;
        Big_Number ret;
        for(int i = SZ - 1; i >= 0; --i){
            int sum = l.a[i] + r.a[i] + add;
            ret.a[i] = sum % 256;
            add = sum / 256;
        }
        return ret;
    }

    friend bool operator<(const Big_Number &l, const Big_Number &r){
        for(int i = 0; i < SZ; ++i)
            if(l.a[i] != r.a[i])
                return l.a[i] < r.a[i];
        return false;
    }
};

static bool done = false;
static Big_Number bc[H][H];

void decode(int n, int l, int x[]){
    if(!done){
        bc[0][0].a[SZ - 1] = 1;
        for(int i = 0; i < H; ++i){
            bc[i][0].a[SZ - 1] = 1;
            for(int j = 1; j <= i; ++j)
                bc[i][j] = bc[i - 1][j] + bc[i - 1][j - 1];
        }
        done = true;
    }

    sort(x, x + l);

    int t = 5 * n, num = 255;
    Big_Number curr;
    for(; t > 0; --t){
        int num = x[t - 1];
        curr = curr + bc[t + num - 1][t];
    }

    for(int i = 0; i < n; ++i)
        output(curr.a[SZ - 1 - i]);
}

Compilation message (stderr)

encoder.cpp:38:13: warning: 'void output_number(Big_Number)' defined but not used [-Wunused-function]
   38 | static void output_number(Big_Number bn){
      |             ^~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:51:20: warning: unused variable 'num' [-Wunused-variable]
   51 |     int t = 5 * n, num = 255;
      |                    ^~~

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