Submission #235583

#	Time	Username	Problem	Language	Result	Execution time	Memory
235583		Coroian_David	Parrots (IOI11_parrots)	C++11	100 / 100	296 ms	98032 KiB

encoder

    #include <bits/stdc++.h>
    #include "encoder.h"
    #include "encoderlib.h"
     
    #define MAX_N 64
     
    using namespace std;
     
    int n;
    void aduna(unsigned char a[], unsigned char b[])
    {
        int i = 1;
        int t = 0;
        for(i = 1; i <= max(a[0], b[0]) || t; i ++)
        {
            a[i] += b[i] + t;
            t = 0;
     
            if(a[i] > 9)
            {
                t = a[i] / 10;
                a[i] %= 10;
            }
        }
     
        a[0] = i - 1;
    }
     
    bool cmp(unsigned char a[], unsigned char 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(unsigned char a[], unsigned char 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(unsigned char a[], unsigned char b[])
    {
        int t = 0;
        for(int i = 1; i <= b[0] || t; i ++)
        {
            int x = (int)a[i] - (int)t - (int)b[i];
     
            t = 0;
            if(x < 0)
            {
                t = 1;
                x += 10;
            }
     
            a[i] = x;
        }
     
        while(a[0] > 1 && a[a[0]] == 0)
            a[0] --;
    }
     
    struct nr
    {
        unsigned char 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);
        }
    };
     
    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 p2;
    nr cod;
    nr s;
     
    int done;
     
    void getDp()
    {
        if(done == 1)
            return;
     
        done = 1;
     
        dp[0][0].v[0] = 1;
        dp[0][0].v[1] = 1;
        sdp[0][0].v[0] = 1;
        sdp[0][0].v[1] = 1;
     
     
       // cout << n << "\n";
     
        int nn = 64;
        for(int i = 0; i < 255; i ++)
        {
            for(int j = 0; j <= nn * 5; j ++)
            {
               // if(i >= 150)
                //cout << i << " " << j << " " << n << "\n";
     
                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(n == 0)
                    cout << dp[i][j].v[0] << " " << dp[i][j].v[1] << " " << dp[i][j].v[2] << "\n";
     
                if(dp[i][j].v[0] != 0)
                {
                    sdp[i + 1][j] += dp[i][j];
     
                    if(j + 256 <= nn * 5)
                        mdp[i + 1][j + 256] += dp[i][j];
                }
            }
        }
    }
     
    void afis(nr a)
    {
        for(int i = a.v[0]; i >= 1; i --)
            cout << (int)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);
        }
     
        memset(p2.v, 0, sizeof(p2.v));
        memset(cod.v, 0, sizeof(cod.v));
        memset(s.v, 0, sizeof(s.v));
     
        p2.v[0] = 1;
        p2.v[1] = 1;
     
        cod.v[0] = 1;
        cod.v[1] = 0;
     
        s.v[0] = 1;
        s.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";
            }
     
            //afis(s);
     
          //  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(unsigned char a[], unsigned char b[])
    {
        int i = 1;
        int t = 0;
        for(i = 1; i <= max(a[0], b[0]) || t; i ++)
        {
            a[i] += b[i] + t;
            t = 0;
     
            if(a[i] > 9)
            {
                t = a[i] / 10;
                a[i] %= 10;
            }
        }
     
        a[0] = i - 1;
    }
     
    bool cmp(unsigned char a[], unsigned char 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(unsigned char a[], unsigned char 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(unsigned char a[], unsigned char b[])
    {
        int t = 0;
        for(int i = 1; i <= b[0] || t; i ++)
        {
            int x = (int)a[i] - (int)t - (int)b[i];
     
            t = 0;
            if(x < 0)
            {
                t = 1;
                x += 10;
            }
     
            a[i] = x;
        }
     
        while(a[0] > 1 && a[a[0]] == 0)
            a[0] --;
    }
     
    struct nr
    {
        unsigned char 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);
        }
    };
     
    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 p2;
    nr cod;
    nr s;
     
    int done;
     
    void getDp()
    {
        if(done == 1)
            return;
     
        done = 1;
     
        dp[0][0].v[0] = 1;
        dp[0][0].v[1] = 1;
        sdp[0][0].v[0] = 1;
        sdp[0][0].v[1] = 1;
     
     
       // cout << n << "\n";
     
        int nn = 64;
        for(int i = 0; i < 255; i ++)
        {
            for(int j = 0; j <= nn * 5; j ++)
            {
               // if(i >= 150)
                //cout << i << " " << j << " " << n << "\n";
     
                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(n == 0)
                    cout << dp[i][j].v[0] << " " << dp[i][j].v[1] << " " << dp[i][j].v[2] << "\n";
     
                if(dp[i][j].v[0] != 0)
                {
                    sdp[i + 1][j] += dp[i][j];
     
                    if(j + 256 <= nn * 5)
                        mdp[i + 1][j + 256] += dp[i][j];
                }
            }
        }
    }
     
     
     
    nr p[600];
    nr sp;
    nr tmp;
     
    int apel;
     
    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 ++)
        {
            int last = 0;
            for(int j = 0; j < ap[i]; j ++)
                s += dp[255 - i - 1][sum - j];
     
            sum -= ap[i];
        }
     
        apel ++;
        if(apel == 1)
        {
            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];
            }
        }
     
        memset(sp.v, 0, sizeof(sp.v));
        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;
            }
        }
     
        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:183:17: warning: unused variable 'last' [-Wunused-variable]
             int last = 0;
                 ^~~~

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