Submission #1053944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053944		oscar1f	Parrots (IOI11_parrots)	C++17	100 / 100	62 ms	32864 KiB

encoder

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

static const int BASE_NB=256,TAILLE_MAX=5*64;
static int tailleMess,nbVal;
static vector<int> memo[TAILLE_MAX][BASE_NB];

static vector<int> somme(vector<int> a,vector<int> b) {
    int retenue=0;
    vector<int> ans;
    for (int i=0;i<(int)max(a.size(),b.size());i++)  {
        if (i<(int)a.size()) {
            retenue+=a[i];
        }
        if (i<(int)b.size()) {
            retenue+=b[i];
        }
        ans.push_back(retenue%BASE_NB);
        retenue/=BASE_NB;
    }
    if (retenue!=0) {
        ans.push_back(retenue);
    }
    return ans;
}

static int ordre(vector<int> a,vector<int> b) {
    if (a.size()>b.size()) {
        return 1;
    }
    if (a.size()<b.size()) {
        return -1;
    }
    for (int i=(int)a.size()-1;i>=0;i--) {
        if (a[i]>b[i]) {
            return 1;
        }
        if (a[i]<b[i]) {
            return -1;
        }
    }
    return 0;
}

static vector<int> dyna(int pos,int dern) {
    if (dern>=BASE_NB) {
        return {};
    }
    if (pos==tailleMess) {
        return {1};
    }
    if (!memo[pos][dern].empty()) {
        return memo[pos][dern];
    }
    memo[pos][dern]=somme(dyna(pos+1,dern),dyna(pos,dern+1));
    return memo[pos][dern];
}

void encode(int N, int M[]) {
    nbVal=N;
    tailleMess=5*nbVal;
    vector<int> envoi,numContract,nbAvant;
    for (int i=0;i<nbVal;i++) {
        numContract.push_back(M[i]);
    }
    while (!numContract.empty() and numContract.back()==0) {
        numContract.pop_back();
    }
    int dern=0;
    for (int i=0;i<tailleMess;i++) {
        while (ordre(somme(nbAvant,dyna(i+1,dern)),numContract)<=0) {
            nbAvant=somme(nbAvant,dyna(i+1,dern));
            dern++;
        }
        envoi.push_back(dern);
    }
    for (int i:envoi) {
        send(i);
    }
}   

decoder

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

static const int BASE_NB=256,TAILLE_MAX=5*64;
static int tailleMess,nbVal;
static vector<int> memo[TAILLE_MAX][BASE_NB];

static vector<int> somme(vector<int> a,vector<int> b) {
    int retenue=0;
    vector<int> ans;
    for (int i=0;i<(int)max(a.size(),b.size());i++)  {
        if (i<(int)a.size()) {
            retenue+=a[i];
        }
        if (i<(int)b.size()) {
            retenue+=b[i];
        }
        ans.push_back(retenue%BASE_NB);
        retenue/=BASE_NB;
    }
    if (retenue!=0) {
        ans.push_back(retenue);
    }
    return ans;
}

static vector<int> dyna(int pos,int dern) {
    if (dern>=BASE_NB) {
        return {};
    }
    if (pos==tailleMess) {
        return {1};
    }
    if (!memo[pos][dern].empty()) {
        return memo[pos][dern];
    }
    memo[pos][dern]=somme(dyna(pos+1,dern),dyna(pos,dern+1));
    return memo[pos][dern];
}


void decode(int N, int L, int X[]) {
    nbVal=N;
    tailleMess=L;
    vector<int> recu;
    for (int i=0;i<tailleMess;i++) {
        recu.push_back(X[i]);
    }
    sort(recu.begin(),recu.end());
    vector<int> ans;
    int dern=0;
    for (int i=0;i<tailleMess;i++) {
        while (dern<recu[i]) {
            ans=somme(ans,dyna(i+1,dern));
            dern++;
        }
    }
    while ((int)ans.size()<nbVal) {
        ans.push_back(0);
    }
    for (int i:ans) {
        output(i);
    }
}

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