Submission #1053931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053931		oscar1f	Parrots (IOI11_parrots)	C++17	81 / 100	1623 ms	35972 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;
}

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();
    }
    for (int i=tailleMess;i>=0;i--) {
        for (int j=BASE_NB-1;j>=0;j--) {
            if (i==tailleMess) {
                memo[i][j]={1};
            }
            else {
                memo[i][j]=memo[i+1][j];
                if (j<BASE_NB-1) {
                    memo[i][j]=somme(memo[i][j],memo[i][j+1]);
                }
            }
        }
    }
    int dern=0;
    for (int i=0;i<tailleMess;i++) {
        while (ordre(somme(nbAvant,memo[i+1][dern]),numContract)<=0) {
            nbAvant=somme(nbAvant,memo[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;
}

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());
    for (int i=tailleMess;i>=0;i--) {
        for (int j=BASE_NB-1;j>=0;j--) {
            if (i==tailleMess) {
                memo[i][j]={1};
            }
            else {
                memo[i][j]=memo[i+1][j];
                if (j<BASE_NB-1) {
                    memo[i][j]=somme(memo[i][j],memo[i][j+1]);
                }
            }
        }
    }
    vector<int> ans;
    int dern=0;
    for (int i=0;i<tailleMess;i++) {
        while (dern<recu[i]) {
            ans=somme(ans,memo[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: 0 / 19