Submission #235571

#	Time	Username	Problem	Language	Result	Execution time	Memory
235571		Coroian_David	Parrots (IOI11_parrots)	C++11	0 / 100	2108 ms	386336 KiB

encoder

        #include "encoder.h"
        #include "encoderlib.h"
        #include <bits/stdc++.h>
         
        #define MAX_N 64
         
        using namespace std;
         
         
        int n;
        void aduna(int a[], int b[])
        {
           // cout << " ADUN " << a[0] << " " << b[0] << "\n";
           // cout << a[1] << " " << b[1] << " " << a[2] << " " << b[2] << "\n";
         
            int i = 1;
            int t = 0;
            for(i = 1; i <= max(a[0], b[0]) || t; i ++)
            {
               // cout << " SUTNEM " << i << "\n";
         
                a[i] += b[i] + t;
                t = 0;
         
                if(a[i] > 9)
                {
                    t = a[i] / 10;
                    a[i] %= 10;
                }
            }
         
            //cout << a[0] << " " << i-1 << "\n";
         
            a[0] = i - 1;
        }
         
        bool cmp(int a[], int b[])
        {
            if(a[0] > b[0])
                return 1;
         
            if(a[0] < b[0])
                return 0;
         
            for(int i = a[0]; i >= 1; i --)
            {
                if(a[i] != b[i])
                    return (a[i] > b[i]);
            }
         
            return 1;
        }
         
        void copyV(int a[], int b[])
        {
            for(int i = 1; i <= a[0]; i ++)
                a[i] = 0;
         
            a[0] = b[0];
            for(int i = 1; i <= b[0]; i ++)
                a[i] = b[i];
        }
         
        void scade(int a[], int b[])
        {
            int t = 0;
            for(int i = 1; i <= b[0] || t; i ++)
            {
                a[i] = a[i] - t - b[i];
                t = 0;
         
                if(a[i] < 0)
                {
                    t = 1;
                    a[i] += 10;
                }
            }
         
            while(a[0] > 1 && a[a[0]] == 0)
                a[0] --;
        }
         
        struct nr
        {
            int v[200];
         
            void operator +=(nr &x)
            {
                aduna(v, x.v);
            }
         
            void operator -=(nr &x)
            {
                scade(v, x.v);
            }
         
            void operator =(nr &x)
            {
                copyV(v, x.v);
            }
         
            bool operator >= (nr &x)
            {
                return cmp(v, x.v);
            }
        };
         
        //#define MAX_N 64
         
        
nr dp[255 + 1][MAX_N * 5 + 1];
nr sdp[255 + 1][MAX_N * 5 + 1];
nr mdp[255 + 1][MAX_N * 5 + 1];

nr a, b;

nr p2;
nr cod;
nr s;
/*
void afis(int a[])
{
    for(int i = a[0]; i >=1; i --)
        cout << a[i];
    cout << "\n";
}*/

void getDp()
{
    dp[0][0].v[0] = 1;
    dp[0][0].v[1] = 1;
    sdp[0][0].v[0] = 1;
    sdp[0][0].v[1] = 1;

    int n = 64;
    for(int i = 0; i < 255; i ++)
    {
        for(int j = 0; j <= n * 5; j ++)
        {
            if(j > 0)
            {
                sdp[i][j] += sdp[i][j - 1];
                mdp[i][j] += mdp[i][j - 1];
            }

            dp[i][j] = sdp[i][j];
            dp[i][j] -= mdp[i][j];

            if(dp[i][j].v[0] != 0)
            {
                sdp[i + 1][j] += dp[i][j];

                if(j + 256 <= n * 5)
                    mdp[i + 1][j + 256] += dp[i][j];
            }
        }
    }
}
        /*
        void afis(nr a)
        {
            for(int i = a.v[0]; i >= 1; i --)
                cout << a.v[i];
            cout << "\n";
        }*/
         
        void encode(int N, int M[])
        {
            n = N;
            getDp();
         
            int k = 0;
            int a[700];
            for(int i = 0; i < N; i ++)
            {
                for(int j = 7; j >= 0; j --)
                    a[++ k] = (((1 << j) & M[i]) != 0);
            }
         
            p2.v[0] = 1;
            p2.v[1] = 1;
         
            cod.v[0] = 1;
            cod.v[1] = 0;
         
            for(int i = k; i >= 1; i --)
            {
                if(a[i] != 0)
                    cod += p2;
         
                p2 += p2;
            }
         
            int sum = 5 * n;
            for(int i = 0; i <= 255; i ++)
            {
                int last = 0;
                for(int j = 0; j <= n * 5 && j <= sum; j ++)
                {
                    //cout << " SUNTEM IN  " << i << "  CR " << j << "\n";
         
                    if(cod >= s)
                        last = j;
         
                    else
                    {
                        s -= dp[255 - i - 1][sum - last];
                        break;
                    }
         
                   // cout << " URM ADUNS \n";
         
                    s += dp[255 - i - 1][sum - j];
         
                   // cout << " GATA ADUN\n";
                }
         
               // cout << " PENTRU FRECVENTA LUI " << i << " ESTE " << last << "\n";
         
                sum -= last;
                for(int j = 1; j <= last; j ++)
                    send(i);
            }
         
            //cout << "RAMAS == 0: " << sum << "\n";
         
            //afis(cod);
           // afis(s);
        }

decoder

        #include "decoder.h"
        #include "decoderlib.h"
        #include <bits/stdc++.h>
         
        #define MAX_N 64
         
        using namespace std;
         
        int n;
        void aduna(int a[], int b[])
        {
           // cout << " ADUN " << a[0] << " " << b[0] << "\n";
           // cout << a[1] << " " << b[1] << " " << a[2] << " " << b[2] << "\n";
         
            int i = 1;
            int t = 0;
            for(i = 1; i <= max(a[0], b[0]) || t; i ++)
            {
               // cout << " SUTNEM " << i << "\n";
         
                a[i] += b[i] + t;
                t = 0;
         
                if(a[i] > 9)
                {
                    t = a[i] / 10;
                    a[i] %= 10;
                }
            }
         
            //cout << a[0] << " " << i-1 << "\n";
         
            a[0] = i - 1;
        }
         
        bool cmp(int a[], int b[])
        {
            if(a[0] > b[0])
                return 1;
         
            if(a[0] < b[0])
                return 0;
         
            for(int i = a[0]; i >= 1; i --)
            {
                if(a[i] != b[i])
                    return (a[i] > b[i]);
            }
         
            return 1;
        }
         
        void copyV(int a[], int b[])
        {
            for(int i = 1; i <= a[0]; i ++)
                a[i] = 0;
         
            a[0] = b[0];
            for(int i = 1; i <= b[0]; i ++)
                a[i] = b[i];
        }
         
        void scade(int a[], int b[])
        {
            int t = 0;
            for(int i = 1; i <= b[0] || t; i ++)
            {
                a[i] = a[i] - t - b[i];
                t = 0;
         
                if(a[i] < 0)
                {
                    t = 1;
                    a[i] += 10;
                }
            }
         
            while(a[0] > 1 && a[a[0]] == 0)
                a[0] --;
        }
         
        struct nr
        {
            int v[200];
         
            void operator +=(nr &x)
            {
                aduna(v, x.v);
            }
         
            void operator -=(nr &x)
            {
                scade(v, x.v);
            }
         
            void operator =(nr &x)
            {
                copyV(v, x.v);
            }
         
            bool operator >= (nr &x)
            {
                return cmp(v, x.v);
            }
        };
         
        //#define MAX_N 64
         
        
nr dp[255 + 1][MAX_N * 5 + 1];
nr sdp[255 + 1][MAX_N * 5 + 1];
nr mdp[255 + 1][MAX_N * 5 + 1];

nr a, b;

nr p2;
nr cod;
nr s;
/*
void afis(int a[])
{
    for(int i = a[0]; i >=1; i --)
        cout << a[i];
    cout << "\n";
}*/

void getDp()
{
    dp[0][0].v[0] = 1;
    dp[0][0].v[1] = 1;
    sdp[0][0].v[0] = 1;
    sdp[0][0].v[1] = 1;

    int n = 64;
    for(int i = 0; i < 255; i ++)
    {
        for(int j = 0; j <= n * 5; j ++)
        {
            if(j > 0)
            {
                sdp[i][j] += sdp[i][j - 1];
                mdp[i][j] += mdp[i][j - 1];
            }

            dp[i][j] = sdp[i][j];
            dp[i][j] -= mdp[i][j];

            if(dp[i][j].v[0] != 0)
            {
                sdp[i + 1][j] += dp[i][j];

                if(j + 256 <= n * 5)
                    mdp[i + 1][j + 256] += dp[i][j];
            }
        }
    }
}
         
         
        nr p[600];
        nr sp;
        nr tmp;
         
        void decode(int N, int L, int X[])
        {
            n = N;
         
            getDp();
         
            int ap[256];
            for(int i = 0; i <= 255; i ++)
                ap[i] = 0;
         
            for(int i = 0; i < L; i ++)
                ap[X[i]] ++;
         
            memset(s.v, 0, sizeof(s.v));
         
            int sum = 5 * n;
            for(int i = 0; i <= 255; i ++)
            {
               // if(ap[i] > 0)
                  //  cout << i <<"APRAE " << ap[i] << "\n";
         
                int last = 0;
                for(int j = 0; j < ap[i]; j ++)
                    s += dp[255 - i - 1][sum - j];
         
                sum -= ap[i];
            }
         
            //cout << " CODUL  ESTE : ";
           // afis(s);
         
            p[0].v[0] = 1;
            p[0].v[1] = 1;
            for(int i = 1; i <= 520; i ++)
            {
                p[i].v[0] = 1;
                p[i].v[1] = 0;
                p[i] += p[i - 1];
                p[i] += p[i - 1];
            }
         
            sp.v[0] = 1;
            sp.v[1] = 0;
         
            int a[600];
            memset(a, 0, sizeof(a));
         
            for(int i = n * 8 - 1; i >= 0; i --)
            {
                tmp = sp;
                tmp += p[i];
                if(s >= tmp)
                {
                    sp += p[i];
                    a[i] = 1;
                }
            }
        //    cout << "\n";
         
            for(int i = n * 8 - 1; i >= 0; i -= 8)
            {
         
                int nr = 0;
                for(int x = 7, j = 0; x >= 0; x --, j ++)
                    nr += (a[i - j] << x);
         
                output(nr);
            }
        }

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:185:21: warning: unused variable 'last' [-Wunused-variable]
                 int last = 0;
                     ^~~~

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