Submission #1053568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053568		oscar1f	Parrots (IOI11_parrots)	C++17	81 / 100	2513 ms	22732 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 vector<int> prod1(vector<int> a,int n,int decal) {
    if (n==0) {
        return {};
    }
    vector<int> ans;
    for (int i=0;i<decal;i++) {
        ans.push_back(0);
    }
    int retenue=0;
    for (int i:a) {
        retenue+=i*n;
        ans.push_back(retenue%BASE_NB);
        retenue/=BASE_NB;
    }
    if (retenue!=0) {
        ans.push_back(retenue);
    }
    return ans;
}

static vector<int> produit(vector<int> a,vector<int> b) {
    if (a.empty() or b.empty()) {
        return {};
    }
    vector<int> ans;
    for (int i=0;i<(int)b.size();i++) {
        ans=somme(ans,prod1(a,b[i],i));
    }
    return ans;
}

static vector<int> puiss(vector<int> a,int expo) {
    if (expo==0) {
        return {1};
    }
    if (expo==1) {
        return a;
    }
    vector<int> ans=puiss(a,expo/2);
    ans=produit(ans,ans);
    if (expo%2==1) {
        ans=produit(ans,a);
    }
    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 (pos==tailleMess) {
        return {1};
    }
    if (!memo[pos][dern].empty()) {
        return memo[pos][dern];
    }
    for (int i=dern;i<BASE_NB;i++) {
        memo[pos][dern]=somme(memo[pos][dern],dyna(pos+1,i));
    }
    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]);
    }
    /*for (int i:numContract) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    while (!numContract.empty() and numContract.back()==0) {
        numContract.pop_back();
    }
    /*for (int i:numContract) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    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);
    }
    //cout<<ordre(nbAvant,numContract)<<endl;
    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> prod1(vector<int> a,int n,int decal) {
    if (n==0) {
        return {};
    }
    vector<int> ans;
    for (int i=0;i<decal;i++) {
        ans.push_back(0);
    }
    int retenue=0;
    for (int i:a) {
        retenue+=i*n;
        ans.push_back(retenue%BASE_NB);
        retenue/=BASE_NB;
    }
    if (retenue!=0) {
        ans.push_back(retenue);
    }
    return ans;
}

static vector<int> produit(vector<int> a,vector<int> b) {
    if (a.empty() or b.empty()) {
        return {};
    }
    vector<int> ans;
    for (int i=0;i<(int)b.size();i++) {
        ans=somme(ans,prod1(a,b[i],i));
    }
    return ans;
}

static vector<int> puiss(vector<int> a,int expo) {
    if (expo==0) {
        return {1};
    }
    if (expo==1) {
        return a;
    }
    vector<int> ans=puiss(a,expo/2);
    ans=produit(ans,ans);
    if (expo%2==1) {
        ans=produit(ans,a);
    }
    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 (pos==tailleMess) {
        return {1};
    }
    if (!memo[pos][dern].empty()) {
        return memo[pos][dern];
    }
    for (int i=dern;i<BASE_NB;i++) {
        memo[pos][dern]=somme(memo[pos][dern],dyna(pos+1,i));
    }
    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());
    /*for (int i:recu) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    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);
    }
}

Compilation message (stderr)

decoder.cpp:75:12: warning: 'int ordre(std::vector<int>, std::vector<int>)' defined but not used [-Wunused-function]
   75 | static int ordre(vector<int> a,vector<int> b) {
      |            ^~~~~

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