Submission #53040

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53040	2018-06-27T19:02:25 Z	SpaimaCarpatilor	Parrots (IOI11_parrots)	C++17	100 / 100	125 ms	37456 KB

encoder

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

static const int baseSz = 29, base = 1 << baseSz;
typedef vector < int > huge;

static bool operator < (huge a, huge 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 a[i] < b[i];return 0;}

static bool operator <= (huge a, huge 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 a[i] < b[i];return 1;}

static bool operator > (huge a, huge 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 a[i] > b[i];return 0;}

static bool operator >= (huge a, huge 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 a[i] > b[i];return 1;}

static bool operator == (huge a, huge b){if (a.size () != b.size ()) return 0;
for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}

static huge operator + (huge a, huge b)
{
    huge ans (max (a.size (), b.size ()), 0);
    int t = 0;
    for (int i=0; i<ans.size (); i++)
    {
        ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
        t = ans[i] / base, ans[i] %= base;
    }
    if (t)
        ans.push_back (t);
    return ans;
}

static huge operator - (huge a, huge b)
{
    huge ans (a.size (), 0);
    int t = 0;
    for (int i=0; i<a.size (); i++)
    {
        ans[i] = a[i] - (i < b.size () ? b[i] : 0) - t;
        if (ans[i] < 0) ans[i] += base, t = 1;
        else t = 0;
    }
    while (!ans.empty () && ans.back () == 0) ans.pop_back ();
    return ans;
}

static void init (huge &x, int val)
{
    x.clear ();
    while (val > 0)
        x.push_back (val % base), val /= base;
}

static void init (huge &x, int sz, int v[])
{
    ///sum of v[i] * 2 ^ i
    x.clear ();
    for (int i=0; i<sz; i+=baseSz)
    {
        int msk = 0;
        for (int j=0; j<baseSz; j++)
            if (v[i + j])
                msk |= 1 << j;
        x.push_back (msk);
    }
    while (!x.empty () && x.back () == 0) x.pop_back ();
}

static bool firstTime = 0;
static huge c[600][600];

void encode(int N, int M[])
{
    if (firstTime == 0)
    {
        firstTime = 1;
        for (int i=0; i<=575; i++)
        {
            init (c[i][0], 1);
            for (int j=1; j<=i; j++)
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    int sz = 0, v[1000], f[260], L = 0;
    for (int i=0; i<N; i++)
        for (int j=0; j<8; j++)
            v[sz ++] = (M[i] >> j) & 1;
    huge pos;
    init (pos, sz, v);
    while (c[L + 255][255] <= pos)
        L ++;
    ///L is fucking optimal
    vector < int > h;
    h.push_back (0);
    for (int i=1, j=0; i<=L + 255; i++)
        if (c[L + 255 - i][255 - j] <= pos)
            pos = pos - c[L + 255 - i][255 - j],
            j ++, h.push_back (i);
    h.push_back (L + 256), sz = 0;
    for (int i=0; i + 1<h.size (); i++)
        f[sz ++] = h[i + 1] - h[i] - 1;
    for (int i=0; i<256; i++)
        while (f[i] --)
            send (i);
}

decoder

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

static const int baseSz = 29, base = 1 << baseSz;
typedef vector < int > huge;

static bool operator < (huge a, huge 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 a[i] < b[i];return 0;}

static bool operator <= (huge a, huge 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 a[i] < b[i];return 1;}

static bool operator > (huge a, huge 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 a[i] > b[i];return 0;}

static bool operator >= (huge a, huge 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 a[i] > b[i];return 1;}

static bool operator == (huge a, huge b){if (a.size () != b.size ()) return 0;
for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}

static huge operator + (huge a, huge b)
{
    huge ans (max (a.size (), b.size ()), 0);
    int t = 0;
    for (int i=0; i<ans.size (); i++)
    {
        ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
        t = ans[i] / base, ans[i] %= base;
    }
    if (t)
        ans.push_back (t);
    return ans;
}

static huge operator - (huge a, huge b)
{
    huge ans (a.size (), 0);
    int t = 0;
    for (int i=0; i<a.size (); i++)
    {
        ans[i] = a[i] - (i < b.size () ? b[i] : 0) - t;
        if (ans[i] < 0) ans[i] += base, t = 1;
        else t = 0;
    }
    while (!ans.empty () && ans.back () == 0) ans.pop_back ();
    return ans;
}

static void init (huge &x, int val)
{
    x.clear ();
    while (val > 0)
        x.push_back (val % base), val /= base;
}

static void init (huge &x, int sz, int v[])
{
    ///sum of v[i] * 2 ^ i
    x.clear ();
    for (int i=0; i<sz; i+=baseSz)
    {
        int msk = 0;
        for (int j=0; j<baseSz; j++)
            if (v[i + j])
                msk |= 1 << j;
        x.push_back (msk);
    }
    while (!x.empty () && x.back () == 0) x.pop_back ();
}

static void printTo (huge &x, int sz, int v[])
{
    int nr = 0;
    for (int i=0; i<x.size (); i++)
        for (int j=0; j<baseSz; j++)
            v[nr ++] = (x[i] >> j) & 1;
    while (nr < sz)
        v[nr ++] = 0;
}

static bool firstTime = 0;
static huge c[600][600];

void decode(int N, int L, int X[])
{
    if (firstTime == 0)
    {
        firstTime = 1;
        for (int i=0; i<=575; i++)
        {
            init (c[i][0], 1);
            for (int j=1; j<=i; j++)
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    ///
    int f[260], h[260 + L];
    for (int i=0; i<256; i++)
        f[i] = 1;
    memset (h, 0, sizeof (h));
    for (int i=0; i<L; i++)
        f[X[i]] ++;
    for (int i=0, j=0; i<255; i++)
        j += f[i], h[j] = 1;
    ///computed h
    huge pos;
    for (int i=1, j=0; i<=L + 255; i++)
        if (h[i])
            pos = pos + c[L + 255 - i][255 - j], j ++;
    ///computed pos
    int v[1000];
    printTo (pos, 8 * N, v);
    for (int j=0; j<8 * N; j+=8)
    {
        int msk = 0;
        for (int k=j; k<j + 8; k++)
            if (v[k])
                msk |= 1 << (k - j);
        output (msk);
    }
}

Compilation message

encoder.cpp: In function 'bool operator<(huge, huge)':
encoder.cpp:10:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 0;}
 ^~~
encoder.cpp:10:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 0;}
                                                                         ^~~~~~
encoder.cpp: In function 'bool operator<=(huge, huge)':
encoder.cpp:13:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 1;}
 ^~~
encoder.cpp:13:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 1;}
                                                                         ^~~~~~
encoder.cpp: In function 'bool operator>(huge, huge)':
encoder.cpp:16:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 0;}
 ^~~
encoder.cpp:16:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 0;}
                                                                         ^~~~~~
encoder.cpp: In function 'bool operator>=(huge, huge)':
encoder.cpp:19:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 1;}
 ^~~
encoder.cpp:19:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 1;}
                                                                         ^~~~~~
encoder.cpp: In function 'bool operator==(huge, huge)':
encoder.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
               ~^~~~~~~~~~
encoder.cpp:22:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
 ^~~
encoder.cpp:22:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
                                                          ^~~~~~
encoder.cpp: In function 'huge operator+(huge, huge)':
encoder.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size (); i++)
                   ~^~~~~~~~~~~~
encoder.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
                   ~~^~~~~~~~~~~
encoder.cpp:30:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
                                                ~~^~~~~~~~~~~
encoder.cpp: In function 'huge operator-(huge, huge)':
encoder.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<a.size (); i++)
                   ~^~~~~~~~~~
encoder.cpp:44:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = a[i] - (i < b.size () ? b[i] : 0) - t;
                          ~~^~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:105:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i + 1<h.size (); i++)
                   ~~~~~^~~~~~~~~~
encoder.cpp: At global scope:
encoder.cpp:21:13: warning: 'bool operator==(huge, huge)' defined but not used [-Wunused-function]
 static bool operator == (huge a, huge b){if (a.size () != b.size ()) return 0;
             ^~~~~~~~
encoder.cpp:18:13: warning: 'bool operator>=(huge, huge)' defined but not used [-Wunused-function]
 static bool operator >= (huge a, huge b){if (a.size () > b.size ()) return 1;if (a.size () < b.size ()) return 0;
             ^~~~~~~~
encoder.cpp:15:13: warning: 'bool operator>(huge, huge)' defined but not used [-Wunused-function]
 static bool operator > (huge a, huge b){if (a.size () > b.size ()) return 1;if (a.size () < b.size ()) return 0;
             ^~~~~~~~
encoder.cpp:9:13: warning: 'bool operator<(huge, huge)' defined but not used [-Wunused-function]
 static bool operator < (huge a, huge b){if (a.size () < b.size ()) return 1;if (a.size () > b.size ()) return 0;
             ^~~~~~~~

decoder.cpp: In function 'bool operator<(huge, huge)':
decoder.cpp:10:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 0;}
 ^~~
decoder.cpp:10:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 0;}
                                                                         ^~~~~~
decoder.cpp: In function 'bool operator<=(huge, huge)':
decoder.cpp:13:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 1;}
 ^~~
decoder.cpp:13:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] < b[i];return 1;}
                                                                         ^~~~~~
decoder.cpp: In function 'bool operator>(huge, huge)':
decoder.cpp:16:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 0;}
 ^~~
decoder.cpp:16:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 0;}
                                                                         ^~~~~~
decoder.cpp: In function 'bool operator>=(huge, huge)':
decoder.cpp:19:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 1;}
 ^~~
decoder.cpp:19:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=a.size () - 1; i>=0; i--)if (a[i] != b[i])return a[i] > b[i];return 1;}
                                                                         ^~~~~~
decoder.cpp: In function 'bool operator==(huge, huge)':
decoder.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
               ~^~~~~~~~~~
decoder.cpp:22:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
 ^~~
decoder.cpp:22:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
 for (int i=0; i<a.size (); i++)if (a[i] != b[i])return 0;return 1;}
                                                          ^~~~~~
decoder.cpp: In function 'huge operator+(huge, huge)':
decoder.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size (); i++)
                   ~^~~~~~~~~~~~
decoder.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
                   ~~^~~~~~~~~~~
decoder.cpp:30:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = (i < a.size () ? a[i] : 0) + (i < b.size () ? b[i] : 0) + t;
                                                ~~^~~~~~~~~~~
decoder.cpp: In function 'huge operator-(huge, huge)':
decoder.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<a.size (); i++)
                   ~^~~~~~~~~~
decoder.cpp:44:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = a[i] - (i < b.size () ? b[i] : 0) - t;
                          ~~^~~~~~~~~~~
decoder.cpp: In function 'void printTo(huge&, int, int*)':
decoder.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<x.size (); i++)
                   ~^~~~~~~~~~
decoder.cpp: At global scope:
decoder.cpp:59:13: warning: 'void init(huge&, int, int*)' defined but not used [-Wunused-function]
 static void init (huge &x, int sz, int v[])
             ^~~~
decoder.cpp:38:13: warning: 'huge operator-(huge, huge)' defined but not used [-Wunused-function]
 static huge operator - (huge a, huge b)
             ^~~~~~~~
decoder.cpp:21:13: warning: 'bool operator==(huge, huge)' defined but not used [-Wunused-function]
 static bool operator == (huge a, huge b){if (a.size () != b.size ()) return 0;
             ^~~~~~~~
decoder.cpp:18:13: warning: 'bool operator>=(huge, huge)' defined but not used [-Wunused-function]
 static bool operator >= (huge a, huge b){if (a.size () > b.size ()) return 1;if (a.size () < b.size ()) return 0;
             ^~~~~~~~
decoder.cpp:15:13: warning: 'bool operator>(huge, huge)' defined but not used [-Wunused-function]
 static bool operator > (huge a, huge b){if (a.size () > b.size ()) return 1;if (a.size () < b.size ()) return 0;
             ^~~~~~~~
decoder.cpp:12:13: warning: 'bool operator<=(huge, huge)' defined but not used [-Wunused-function]
 static bool operator <= (huge a, huge b){if (a.size () < b.size ()) return 1;if (a.size () > b.size ()) return 0;
             ^~~~~~~~
decoder.cpp:9:13: warning: 'bool operator<(huge, huge)' defined but not used [-Wunused-function]
 static bool operator < (huge a, huge b){if (a.size () < b.size ()) return 1;if (a.size () > b.size ()) return 0;
             ^~~~~~~~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	36088 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	36448 KB	Output is correct
2	Correct	93 ms	36680 KB	Output is correct
3	Correct	90 ms	36680 KB	Output is correct
4	Correct	95 ms	36680 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	36728 KB	Output is correct
2	Correct	125 ms	36816 KB	Output is correct
3	Correct	91 ms	36904 KB	Output is correct
4	Correct	93 ms	37136 KB	Output is correct

Subtask #4

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	37136 KB	Output is correct
2	Correct	92 ms	37136 KB	Output is correct
3	Correct	92 ms	37136 KB	Output is correct
4	Correct	91 ms	37136 KB	Output is correct
5	Correct	93 ms	37224 KB	Output is correct
6	Correct	94 ms	37304 KB	Output is correct

Subtask #5

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	37304 KB	Output is correct - P = 1.750000
2	Correct	92 ms	37304 KB	Output is correct - P = 2.437500
3	Correct	92 ms	37304 KB	Output is correct - P = 2.484848
4	Correct	100 ms	37408 KB	Output is correct - P = 3.360000
5	Correct	101 ms	37408 KB	Output is correct - P = 4.050000
6	Correct	121 ms	37456 KB	Output is correct - P = 4.301587
7	Correct	116 ms	37456 KB	Output is correct - P = 4.234375