Submission #512613

#	Time	Username	Problem	Language	Result	Execution time	Memory
512613		kripton2005	Parrots (IOI11_parrots)	C++14	100 / 100	7 ms	1320 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--;
        }
        assert(par == 1);
        assert((int) vec.size() == c1);
        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]); else assert(vec[i] == 16);
        }
    }
}

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