Submission #360865

#	Time	Username	Problem	Language	Result	Execution time	Memory
360865		79brue	Parrots (IOI11_parrots)	C++14	100 / 100	9 ms	1532 KiB

encoder

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

using namespace std;

typedef long long ll;

namespace{
    int n;
    ll arr[102];
    ll comb[52][52];

    int const1[] = {5, 10, 15, 20};
    int const2[] = {16+5, 16+10, 16+15, 16+20};
}

void encode(int N, int M[]){
    comb[0][0] = 1LL;
    for(int i=1; i<=50; i++){
        comb[i][0] = comb[i][i] = 1LL;
        for(int j=1; j<i; j++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
        }
    }

    n = N;
    memset(arr, 0, sizeof(arr));
    for(int i=0; i<n; i++){
        int tmp = M[i];
        arr[i] = tmp;
    }

    for(int c=0; c<n; c+=4){
        int tConst = (c+4 < n ? 4 : n-c);
        int c1 = const1[tConst-1];
        int c2 = const2[tConst-1];

        ll par = (arr[c+3]<<24LL) + (arr[c+2]<<16LL) + (arr[c+1]<<8LL) + arr[c] + 1;
        vector<int> vec;
        int leftK = c1;
        for(int i=0; i<c2 && leftK; i++){
            if(par <= comb[c2-1-i][leftK]){
                continue;
            }
            par -= comb[c2-1-i][leftK];
            vec.push_back(i);
            leftK--;
        }
        for(int i=0; i<c1; i++) vec[i] -= i;
        for(int i=0; i<c1; i++){
            if(vec[i] < 16) send((c/4) * 16 + vec[i]);
        }
    }
}

decoder

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

using namespace std;

typedef long long ll;

namespace {
    int n, k;
    ll arr[102];
    ll code[200002];
    ll comb[52][52];
    int const1[] = {5, 10, 15, 20};
    int const2[] = {16+5, 16+10, 16+15, 16+20};
}

void decode(int N, int L, int X[]){
    comb[0][0] = 1;
    for(int i=1; i<=50; i++){
        comb[i][0] = comb[i][i] = 1;
        for(int j=1; j<i; j++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
        }
    }

    memset(arr, 0, sizeof(arr));
    n = N, k = L;
    for(int i=0; i<k; i++) code[i] = X[i];
    sort(code, code+k);

    int pnt = 0;
    for(int c=0; c<n; c+=4){
        int tConst = (c+4 < n ? 4 : n-c);
        int c1 = const1[tConst-1];
        int c2 = const2[tConst-1];

        vector<int> codes;
        while(pnt < k && code[pnt]/16 == c/4){
            codes.push_back(code[pnt]%16);
            pnt++;
        }
        while((int)codes.size() < c1) codes.push_back(16);
        for(int i=0; i<c1; i++) codes[i] += i;

        ll parm = 0;
        for(int i=0; i<c1; i++){
            parm += comb[c2-1-codes[i]][c1-i];
        }

        arr[c+3] = parm >> 24;
        arr[c+2] = (parm >> 16) & 255;
        arr[c+1] = (parm >> 8) & 255;
        arr[c] = parm & 255;
    }

    for(int i=0; i<n; i++){
        output(arr[i]);
    }
}

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