Submission #125596

#	Time	Username	Problem	Language	Result	Execution time	Memory
125596		thebes	Parrots (IOI11_parrots)	C++14	100 / 100	11 ms	1776 KiB

encoder

#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;

typedef long long ll;
ll dp[22][20], i, j;
ll cmp(ll len,ll lst){
    if(len==0) return 1LL;
    else if(dp[len][lst]) return dp[len][lst];
    for(int i=lst;i<=16;i++)
        dp[len][lst]+=cmp(len-1,i);
    return dp[len][lst];
}
void enc(ll idx,ll wtf,ll len,ll lst){
    if(!len) return;
    for(ll i=lst;i<=16;i++){
        if(cmp(len,i+1)<=wtf){
            if(i<16) send((idx<<4)+i);
            wtf -= cmp(len,i+1);
            enc(idx, wtf, len-1, i);
            return;
        }
    }
}
void encode(int N,int *M){
    for(i=0;i<N;i+=4){
        ll heh = 0;
        for(j=0;j<4&&i+j<N;j++)
            heh += (1LL<<(j*8))*M[i+j];
        enc(i>>2,heh,5*j,0);
    }
}

decoder

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;

typedef long long ll;
ll dp[22][20], i, j;
ll cmp(ll len,ll lst){
    if(len==0) return 1LL;
    else if(dp[len][lst]) return dp[len][lst];
    for(int i=lst;i<=16;i++)
        dp[len][lst]+=cmp(len-1,i);
    return dp[len][lst];
}
vector<int> heh[200];
ll dec(ll len,ll lst,ll id){
    if(len==0) return 0LL;
    ll ret = 0, idx = heh[id].size()-len;
    ret = cmp(len,heh[id][idx]+1);
    return ret+dec(len-1,heh[id][idx],id);
}
void decode(int N,int L,int *M){
  	for(i=0;i<200;i++) heh[i].clear();
    for(i=0;i<L;i++){
        ll idx = (M[i]>>4);
        heh[idx].push_back(M[i]&15);
    }
    for(i=0;i<ceil(N/4.0);i++){
        ll len = 5*min(N-4*i,4LL);
        while(heh[i].size()<len) heh[i].push_back(16);
        sort(heh[i].begin(),heh[i].end());
    }
    for(i=0;i<ceil(N/4.0);i++){
        ll len = min(N-4*i,4LL);
        ll wtf = dec(5*len,0,i);
        for(j=0;j<len;j++){
            output(wtf%256);
            wtf/=256;
        }
    }
}

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:30:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(heh[i].size()<len) heh[i].push_back(16);
               ~~~~~~~~~~~~~^~~~

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