Submission #254346

#	Time	Username	Problem	Language	Result	Execution time	Memory
254346		MKopchev	Parrots (IOI11_parrots)	C++14	100 / 100	200 ms	61936 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

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

const int MX=600;

vector<int> COMB[MX][MX];
/*
int ARR[1000],p=0;
void send(int s)
{
    ARR[p]=s;
    p++;

    cout<<s<<endl;
}
void output(int s)
{
    cout<<"output "<<s<<endl;
}
*/
vector<int> normal(vector<int> a)
{
    int pos=0;

    while(pos<a.size())
    {
        if(0<=a[pos]&&a[pos]<=9)
        {
            pos++;
            continue;
        }

        if(pos+1==a.size())a.push_back(0);

        a[pos+1]+=a[pos]/10;
        a[pos]=a[pos]%10;

        if(a[pos]<0)
        {
            a[pos+1]--;
            a[pos]+=10;
        }

    }

    pos--;
    while(pos>0&&a[pos]==0)
    {
        a.pop_back();
        pos--;
    }
    return a;
}
vector<int> my_add(vector<int> a,vector<int> b)
{
    if(a.size()<b.size())swap(a,b);

    for(int i=0;i<b.size();i++)a[i]+=b[i];

    return normal(a);
}

vector<int> my_sub(vector<int> a,vector<int> b)
{
    for(int i=0;i<b.size();i++)a[i]-=b[i];

    return normal(a);
}

vector<int> my_mult(vector<int> a,int m)
{
    for(auto &k:a)k=k*m;
    return normal(a);
}

int my_mod(vector<int> a,int m)
{
    int ret=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        ret=ret*10+a[i];
        ret=ret%m;
    }
    return ret;
}

vector<int> my_div(vector<int> a,int m)
{
    int mem=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        mem=mem*10+a[i];

        a[i]=mem/m;

        mem=mem%m;
    }
    return normal(a);
}
vector<int> ask(int n,int k)
{
    if(k==n||k==0)return {1};
    if(COMB[n][k].size())return COMB[n][k];

    COMB[n][k]=my_add(ask(n-1,k),ask(n-1,k-1));

    return COMB[n][k];
}

bool more(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 0;
}

bool at_least(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 1;
}

void encode(int N, int M[])
{
    vector<int> which={0};
    for(int i=0;i<N;i++)
    {
        which=my_mult(which,256);
        which=my_add(which,{M[i]});
    }

    int sz=0;

    for(sz=0;more(ask(255+sz,sz),which)==0;sz++);

    //for(auto k:which)cout<<k;cout<<endl;
    //for(auto k:ask(255+sz,sz))cout<<k;cout<<endl;

    int lst=0;

    for(int i=1;i<=sz;i++)
    {
        int give=255-lst,pass=sz-i;

        vector<int> cur=ask(give+pass,pass);

        if(at_least(which,cur))
        {
            lst++;

            which=my_sub(which,cur);

            i--;
            continue;
        }

        //cout<<"sending "<<lst<<endl;
        send(lst);

        assert(0<=lst&&lst<=255);
    }

    //cout<<"sz= "<<sz<<endl;
}

decoder

#include "decoder.h"
#include "decoderlib.h"

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

const int MX=600;

vector<int> COMB[MX][MX];
/*
int ARR[1000],p=0;
void send(int s)
{
    ARR[p]=s;
    p++;

    cout<<s<<endl;
}
void output(int s)
{
    cout<<"output "<<s<<endl;
}
*/
vector<int> normal(vector<int> a)
{
    int pos=0;

    while(pos<a.size())
    {
        if(0<=a[pos]&&a[pos]<=9)
        {
            pos++;
            continue;
        }

        if(pos+1==a.size())a.push_back(0);

        a[pos+1]+=a[pos]/10;
        a[pos]=a[pos]%10;

        if(a[pos]<0)
        {
            a[pos+1]--;
            a[pos]+=10;
        }

    }

    pos--;
    while(pos>0&&a[pos]==0)
    {
        a.pop_back();
        pos--;
    }
    return a;
}
vector<int> my_add(vector<int> a,vector<int> b)
{
    if(a.size()<b.size())swap(a,b);

    for(int i=0;i<b.size();i++)a[i]+=b[i];

    return normal(a);
}

vector<int> my_sub(vector<int> a,vector<int> b)
{
    for(int i=0;i<b.size();i++)a[i]-=b[i];

    return normal(a);
}

vector<int> my_mult(vector<int> a,int m)
{
    for(auto &k:a)k=k*m;
    return normal(a);
}

int my_mod(vector<int> a,int m)
{
    int ret=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        ret=ret*10+a[i];
        ret=ret%m;
    }
    return ret;
}

vector<int> my_div(vector<int> a,int m)
{
    int mem=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        mem=mem*10+a[i];

        a[i]=mem/m;

        mem=mem%m;
    }
    return normal(a);
}
vector<int> ask(int n,int k)
{
    if(k==n||k==0)return {1};
    if(COMB[n][k].size())return COMB[n][k];

    COMB[n][k]=my_add(ask(n-1,k),ask(n-1,k-1));

    return COMB[n][k];
}

bool more(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 0;
}

bool at_least(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 1;
}

void decode(int N, int L, int X[])
{
    vector<int> which={0};

    sort(X,X+L);

    int lst=0;

    for(int i=0;i<L;i++)
    {
        if(X[i]==lst)continue;

        int give=255-lst,pass=L-i-1;

        vector<int> cur=ask(give+pass,pass);

        which=my_add(which,cur);

        lst++;
        i--;
    }

    //for(auto k:which)cout<<k;cout<<endl;

    vector<int> outp={};
    for(int i=0;i<N;i++)outp.push_back(0);

    for(int i=N-1;i>=0;i--)
    {
        outp[i]=my_mod(which,256);

        which=my_div(which,256);
    }

    for(int i=0;i<N;i++)
        output(outp[i]);
}

Compilation message (stderr)

encoder.cpp: In function 'std::vector<int> normal(std::vector<int>)':
encoder.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<a.size())
           ~~~^~~~~~~~~
encoder.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos+1==a.size())a.push_back(0);
            ~~~~~^~~~~~~~~~
encoder.cpp: In function 'std::vector<int> my_add(std::vector<int>, std::vector<int>)':
encoder.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]+=b[i];
                 ~^~~~~~~~~
encoder.cpp: In function 'std::vector<int> my_sub(std::vector<int>, std::vector<int>)':
encoder.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]-=b[i];
                 ~^~~~~~~~~

decoder.cpp: In function 'std::vector<int> normal(std::vector<int>)':
decoder.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<a.size())
           ~~~^~~~~~~~~
decoder.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos+1==a.size())a.push_back(0);
            ~~~~~^~~~~~~~~~
decoder.cpp: In function 'std::vector<int> my_add(std::vector<int>, std::vector<int>)':
decoder.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]+=b[i];
                 ~^~~~~~~~~
decoder.cpp: In function 'std::vector<int> my_sub(std::vector<int>, std::vector<int>)':
decoder.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]-=b[i];
                 ~^~~~~~~~~

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