Submission #895632

#	Time	Username	Problem	Language	Result	Execution time	Memory
895632		abcvuitunggio	Parrots (IOI11_parrots)	C++17	100 / 100	59 ms	15256 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=1000000000;
static struct bignum{
    vector <int> d;
}dp[301][301];
static bignum f(int x){
    if (!x)
        return {{0}};
    bignum a;
    for (;x;x/=base)
        a.d.push_back(x%base);
    return a;
}
static bool operator <(bignum a, bignum b){
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    while (b.d.size()<a.d.size())
        b.d.push_back(0);
    for (int i=a.d.size()-1;i>=0;i--)
        if (a.d[i]!=b.d[i])
            return a.d[i]<b.d[i];
    return false;
}
static bignum operator +(bignum a, bignum b){
    bignum c;
    if (a.d.size()>b.d.size())
        swap(a,b);
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]+b.d[i]+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    if (carry)
        c.d.push_back(carry);
    return c;
}
static bignum operator -(bignum a, bignum b){
    bignum c;
    while (a.d.size()>b.d.size())
        b.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]-b.d[i]-carry;
        if (x<0){
            x+=base;
            carry=1;
        }
        else
            carry=0;
        c.d.push_back(x);
    }
    return c;
}
static bignum operator *(bignum a, int b){
    bignum c;
    long long carry=0;
    for (int i=0;i<a.d.size();i++){
        long long x=1LL*a.d[i]*b+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    for (;carry;carry/=base)
        c.d.push_back(carry%base);
    return c;
}
static bignum calc(int i, int j){
    if (i<0)
        return {{0}};
    if (j<0)
        return {{1}};
    if (!dp[i][j].d.empty())
        return dp[i][j];
    return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void encode(int N, int M[]){
    bignum val={{0}};
    for (int i=N-1;i>=0;i--)
        val=val*256+f(M[i]);
    int n=0,i=0;
    while (calc(255,n)<val)
        n++;
    for (int j=0;j<=n;j++){
        while (calc(255-i,n-j-1)-f(1)<val){
            val=val-calc(255-i,n-j-1);
            i++;
        }
        send(i);
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=1000000000;
static struct bignum{
    vector <int> d;
}dp[301][301];
static bignum f(int x){
    if (!x)
        return {{0}};
    bignum a;
    for (;x;x/=base)
        a.d.push_back(x%base);
    return a;
}
static bignum operator +(bignum a, bignum b){
    bignum c;
    if (a.d.size()>b.d.size())
        swap(a,b);
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]+b.d[i]+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    if (carry)
        c.d.push_back(carry);
    return c;
}
static bignum operator -(bignum a, bignum b){
    bignum c;
    while (a.d.size()>b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]-b.d[i]-carry;
        if (x<0){
            x+=base;
            carry=1;
        }
        c.d.push_back(x);
    }
    return c;
}
static pair <bignum, int> operator /(bignum a, int b){
    bignum c;
    int carry=0;
    for (int i=a.d.size()-1;i>=0;i--){
        long long x=1LL*carry*base+a.d[i];
        if (x/b||!c.d.empty())
            c.d.push_back(x/b);
        carry=x%b;
    }
    reverse(c.d.begin(),c.d.end());
    return {c,carry};
}
static bignum calc(int i, int j){
    if (i<0||j<0)
        return {{0}};
    if (!i&&!j)
        return {{1}};
    if (!dp[i][j].d.empty())
        return dp[i][j];
    return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void decode(int N, int L, int X[]){
    sort(X,X+L);
    bignum val={{0}};
    for (int i=0;i<L;i++)
        for (int j=(i?X[i-1]:0);j<X[i];j++)
            val=val+calc(255-j,L-i-1);
    while (N--){
        auto [q,r]=val/256;
        output(r);
        val=q;
    }
}

Compilation message (stderr)

encoder.cpp: In function 'bignum operator+(bignum, bignum)':
encoder.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator-(bignum, bignum)':
encoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator*(bignum, int)':
encoder.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~

decoder.cpp: In function 'bignum operator+(bignum, bignum)':
decoder.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
decoder.cpp: In function 'bignum operator-(bignum, bignum)':
decoder.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
decoder.cpp: At global scope:
decoder.cpp:33:15: warning: 'bignum operator-(bignum, bignum)' defined but not used [-Wunused-function]
   33 | static bignum operator -(bignum a, bignum b){
      |               ^~~~~~~~
decoder.cpp:9:15: warning: 'bignum f(int)' defined but not used [-Wunused-function]
    9 | static bignum f(int x){
      |               ^

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