Submission #235582

#	Time	Username	Problem	Language	Result	Execution time	Memory
235582		Coroian_David	Parrots (IOI11_parrots)	C++11	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

#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);
}

#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];
            }
        }
    }
}

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);
}



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 encode(int, int*)':
decoder.cpp:228:13: error: 'send' was not declared in this scope
             send(i);
             ^~~~
decoder.cpp:228:13: note: suggested alternative: 'setns'
             send(i);
             ^~~~
             setns
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:263:13: warning: unused variable 'last' [-Wunused-variable]
         int last = 0;
             ^~~~