Submission #1008649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008649		biank	Parrots (IOI11_parrots)	C++14	0 / 100	270 ms	29684 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
struct Bigint {
    string a;
    int sign;
 
    Bigint(){}
    void operator = (string b) {
        a= (b[0]=='-' ? b.substr(1) : b);
        reverse(a.begin(), a.end());
        (*this).Remove0(b[0]=='-' ? -1 : 1);
    }
    Bigint(string x) {(*this)=x;}
    Bigint(ll x) {(*this)=to_string(x);}
    void operator = (ll x){*this=to_string(x);}
 
    char operator[](int i){return a[i];}
    int size() {return a.size();}
    Bigint inverseSign() {sign*=-1; return (*this);}
 
    Bigint Remove0(int newSign) {
        sign = newSign;
        for(int i=a.size()-1; i>0 && a[i]=='0'; i--) a.pop_back();
        if(a.size()==1 && a[0]=='0') sign=1;
        return (*this);
    }
 
    bool operator == (Bigint x) {return sign==x.sign && a==x.a;}
    bool operator == (string x) {return *this==Bigint(x);}
    bool operator == (ll x)     {return *this==Bigint(x);}
    bool operator != (Bigint x) {return !(*this==x);}
    bool operator != (string x) {return !(*this==x);}
    bool operator != (ll x)     {return !(*this==x);}
 
    bool operator < (Bigint b) {
        if (sign!=b.sign) return sign<b.sign;
        if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
        for(int i=a.size()-1; i>=0; i--)
            if(a[i] != b[i]) return a[i]<b[i];
        return false;
    }
    bool operator <  (string x) {return *this<Bigint(x);}
    bool operator <  (ll x)     {return *this<Bigint(x);}
    bool operator <= (Bigint b) {return *this==b || *this<b;}
    bool operator <= (string b) {return *this==b || *this<b;}
    bool operator <= (ll b)     {return *this==b || *this<b;}
    bool operator >  (Bigint b) {return !(*this==b || *this<b);}
    bool operator >  (string x) {return !(*this==x || *this<x);}
    bool operator >  (ll b)     {return !(*this==b || *this<b);}
    bool operator >= (Bigint b) {return *this==b || *this>b;}
    bool operator >= (string b) {return *this==b || *this>b;}
    bool operator >= (ll b)     {return *this==b || *this>b;}
 
    Bigint operator + (Bigint b) {
        if(sign != b.sign) return (*this)-b.inverseSign();
        Bigint sum;
        for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
            if (i<a.size()) carry+=a[i]-'0';
            if (i<b.size()) carry+=b[i]-'0';
            sum.a += (carry % 10 + 48);
            carry /= 10;
        }
        return sum.Remove0(sign);
    }
    Bigint operator +  (string x) {return *this+Bigint(x);}
    Bigint operator +  (ll x)     {return *this+Bigint(x);}
    Bigint operator ++ (int) {*this+=1; return *this-1;}
    Bigint operator ++ ()    {*this+=1; return *this;}
      void operator += (Bigint x) {*this = *this+x;}
      void operator += (string x) {*this = *this+x;}
      void operator += (ll x)     {*this = *this+x;}
 
 
    Bigint operator - ( Bigint b ) {
        if(sign != b.sign) return (*this)+b.inverseSign();
        if(*this < b) return (b - *this).inverseSign();
        Bigint sub;
        for(int i=0,borrow=0; i<a.size(); i++) {
            borrow = a[i]-borrow-(i<b.size() ? b.a[i] : '0');
            sub.a += borrow>=0 ? borrow+'0' : borrow + 58;
            borrow = borrow>=0 ? 0:1;
        }
        return sub.Remove0(sign);
    }
    Bigint operator - (string x) {return *this-Bigint(x);}
    Bigint operator - (ll x)     {return *this-Bigint(x);}
    Bigint operator -- (int) {*this-=1; return *this+1;}
    Bigint operator -- ()    {*this-=1; return *this;}
      void operator -= (Bigint x) {*this = *this-x;}
      void operator -= (string x) {*this = *this-x;}
      void operator -= (ll x)     {*this = *this-x;}
 
    Bigint operator * (Bigint b) {
        Bigint mult("0");
        for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
            while(k-- -'0') mult=mult+b;
            b.a.insert(b.a.begin(),'0');
        }
        return mult.Remove0(sign * b.sign);
    }
    Bigint operator * (string x) {return *this*Bigint(x);}
    Bigint operator * (ll x)     {return *this*Bigint(x);}
      void operator *= (Bigint x) {*this = *this*x;}
      void operator *= (string x) {*this = *this*x;}
      void operator *= (ll x)     {*this = *this*x;}
 
    Bigint operator / (Bigint b) {
        if(b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0');
        Bigint c("0"), d;
        for(int j=0; j<a.size(); j++) d.a += "0";
        int dSign = sign*b.sign; b.sign=1;
        for(int i=a.size()-1; i>=0; i--) {
            c.a.insert(c.a.begin(),'0');
            c=c+a.substr(i,1);
            while(!(c<b)) c=c-b, d.a[i]++;
        }
        return d.Remove0(dSign);
    }
    Bigint operator / (string x) {return *this/Bigint(x);}
    Bigint operator / (ll x)     {return *this/Bigint(x);}
      void operator /= (Bigint x) {*this = *this/x;}
      void operator /= (string x) {*this = *this/x;}
      void operator /= (ll x)     {*this = *this/x;}
 
    Bigint operator % (Bigint b) {
        if( b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0') ;
        Bigint c("0");
        int cSign = sign*b.sign; b.sign=1;
        for( int i=a.size()-1; i>=0; i-- ) {
            c.a.insert( c.a.begin(),'0');
            c = c+a.substr(i,1);
            while(!(c<b)) c=c-b;
        }
        return c.Remove0(cSign);
    }
    Bigint operator % (string x) {return *this%Bigint(x);}
    Bigint operator % (ll x)     {return *this%Bigint(x);}
      void operator %= (Bigint x) {*this = *this%x;}
      void operator %= (string x) {*this = *this%x;}
      void operator %= (ll x)     {*this = *this%x;}
 
    void print() {
        if(sign==-1) putchar('-');
        for(int i=a.size()-1; i>=0; i--) putchar(a[i]);
    }
    friend istream& operator >>(istream &in,Bigint &x){
        string s; in>>s; x=s; return in;
    }
    friend ostream& operator <<(ostream &out,Bigint &x){
        if(x.sign==-1) putchar('-');
        for(int i=x.size()-1; i>=0; i--)
            putchar(x[i]);
        return out;
    }
 
    friend Bigint pow(Bigint base, Bigint pw){
        Bigint ans=1;
        while(pw!=0){
            if(pw%2 !=0) ans*=base;
            base*=base, pw/=2;
        }
        return ans;
    }
    friend Bigint pow(Bigint a, Bigint b,Bigint mod) {
        if (b==0) return Bigint(1);
        Bigint tmp=pow(a,b/2,mod);
        if ((b%2)==0) return (tmp*tmp)%mod;
        else return (((tmp*tmp)%mod)*a)%mod;
    }
    friend Bigint sqrt(Bigint x) {
        Bigint ans=x,tmp=(x+1)/2;
        while (tmp<ans) ans=tmp, tmp=(tmp+x/tmp)/2;
        return ans;
    }
    friend Bigint gcd(Bigint a,Bigint b){
        return a%b==0 ? b : gcd(b, a%b);
    }
    friend Bigint lcm(Bigint a,Bigint b){
        return a/gcd(a,b);
    }
};
 
const int MAXN = 350;
const int MAXA = 255;
 
Bigint dp[MAXN][MAXA];
bool flag = false;
 
void calcDP() {
    for (int i = 0; i < MAXA; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < MAXN; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < MAXA; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXA; j++) {
            cerr << dp[i][j] << ' ';
        }
        cerr << '\n';
    }
    flag = true;
}
 
void encode(int N, int M[]) {
    if (!flag) calcDP();
    Bigint pos = 0;
    for (int i = 0; i < N; i++) {
        pos = pos * 256 + M[i];
    }
    pos++;
    for (int i = 5 * N - 1; i >= 0; i--) {
        int j = 0;
        while (pos >= dp[i][j]) {
            pos -= dp[i][j];
            j++;
        }
        send(j);
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
struct Bigint_de {
    string a;
    int sign;
 
    Bigint_de(){}
    void operator = (string b) {
        a= (b[0]=='-' ? b.substr(1) : b);
        reverse(a.begin(), a.end());
        (*this).Remove0(b[0]=='-' ? -1 : 1);
    }
    Bigint_de(string x) {(*this)=x;}
    Bigint_de(ll x) {(*this)=to_string(x);}
    void operator = (ll x){*this=to_string(x);}
 
    char operator[](int i){return a[i];}
    int size() {return a.size();}
    Bigint_de inverseSign() {sign*=-1; return (*this);}
 
    Bigint_de Remove0(int newSign) {
        sign = newSign;
        for(int i=a.size()-1; i>0 && a[i]=='0'; i--) a.pop_back();
        if(a.size()==1 && a[0]=='0') sign=1;
        return (*this);
    }
 
    bool operator == (Bigint_de x) {return sign==x.sign && a==x.a;}
    bool operator == (string x) {return *this==Bigint_de(x);}
    bool operator == (ll x)     {return *this==Bigint_de(x);}
    bool operator != (Bigint_de x) {return !(*this==x);}
    bool operator != (string x) {return !(*this==x);}
    bool operator != (ll x)     {return !(*this==x);}
 
    bool operator < (Bigint_de b) {
        if (sign!=b.sign) return sign<b.sign;
        if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
        for(int i=a.size()-1; i>=0; i--)
            if(a[i] != b[i]) return a[i]<b[i];
        return false;
    }
    bool operator <  (string x) {return *this<Bigint_de(x);}
    bool operator <  (ll x)     {return *this<Bigint_de(x);}
    bool operator <= (Bigint_de b) {return *this==b || *this<b;}
    bool operator <= (string b) {return *this==b || *this<b;}
    bool operator <= (ll b)     {return *this==b || *this<b;}
    bool operator >  (Bigint_de b) {return !(*this==b || *this<b);}
    bool operator >  (string x) {return !(*this==x || *this<x);}
    bool operator >  (ll b)     {return !(*this==b || *this<b);}
    bool operator >= (Bigint_de b) {return *this==b || *this>b;}
    bool operator >= (string b) {return *this==b || *this>b;}
    bool operator >= (ll b)     {return *this==b || *this>b;}
 
    Bigint_de operator + (Bigint_de b) {
        if(sign != b.sign) return (*this)-b.inverseSign();
        Bigint_de sum;
        for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
            if (i<a.size()) carry+=a[i]-'0';
            if (i<b.size()) carry+=b[i]-'0';
            sum.a += (carry % 10 + 48);
            carry /= 10;
        }
        return sum.Remove0(sign);
    }
    Bigint_de operator +  (string x) {return *this+Bigint_de(x);}
    Bigint_de operator +  (ll x)     {return *this+Bigint_de(x);}
    Bigint_de operator ++ (int) {*this+=1; return *this-1;}
    Bigint_de operator ++ ()    {*this+=1; return *this;}
      void operator += (Bigint_de x) {*this = *this+x;}
      void operator += (string x) {*this = *this+x;}
      void operator += (ll x)     {*this = *this+x;}
 
 
    Bigint_de operator - ( Bigint_de b ) {
        if(sign != b.sign) return (*this)+b.inverseSign();
        if(*this < b) return (b - *this).inverseSign();
        Bigint_de sub;
        for(int i=0,borrow=0; i<a.size(); i++) {
            borrow = a[i]-borrow-(i<b.size() ? b.a[i] : '0');
            sub.a += borrow>=0 ? borrow+'0' : borrow + 58;
            borrow = borrow>=0 ? 0:1;
        }
        return sub.Remove0(sign);
    }
    Bigint_de operator - (string x) {return *this-Bigint_de(x);}
    Bigint_de operator - (ll x)     {return *this-Bigint_de(x);}
    Bigint_de operator -- (int) {*this-=1; return *this+1;}
    Bigint_de operator -- ()    {*this-=1; return *this;}
      void operator -= (Bigint_de x) {*this = *this-x;}
      void operator -= (string x) {*this = *this-x;}
      void operator -= (ll x)     {*this = *this-x;}
 
    Bigint_de operator * (Bigint_de b) {
        Bigint_de mult("0");
        for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
            while(k-- -'0') mult=mult+b;
            b.a.insert(b.a.begin(),'0');
        }
        return mult.Remove0(sign * b.sign);
    }
    Bigint_de operator * (string x) {return *this*Bigint_de(x);}
    Bigint_de operator * (ll x)     {return *this*Bigint_de(x);}
      void operator *= (Bigint_de x) {*this = *this*x;}
      void operator *= (string x) {*this = *this*x;}
      void operator *= (ll x)     {*this = *this*x;}
 
    Bigint_de operator / (Bigint_de b) {
        if(b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0');
        Bigint_de c("0"), d;
        for(int j=0; j<a.size(); j++) d.a += "0";
        int dSign = sign*b.sign; b.sign=1;
        for(int i=a.size()-1; i>=0; i--) {
            c.a.insert(c.a.begin(),'0');
            c=c+a.substr(i,1);
            while(!(c<b)) c=c-b, d.a[i]++;
        }
        return d.Remove0(dSign);
    }
    Bigint_de operator / (string x) {return *this/Bigint_de(x);}
    Bigint_de operator / (ll x)     {return *this/Bigint_de(x);}
      void operator /= (Bigint_de x) {*this = *this/x;}
      void operator /= (string x) {*this = *this/x;}
      void operator /= (ll x)     {*this = *this/x;}
 
    Bigint_de operator % (Bigint_de b) {
        if( b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0') ;
        Bigint_de c("0");
        int cSign = sign*b.sign; b.sign=1;
        for( int i=a.size()-1; i>=0; i-- ) {
            c.a.insert( c.a.begin(),'0');
            c = c+a.substr(i,1);
            while(!(c<b)) c=c-b;
        }
        return c.Remove0(cSign);
    }
    Bigint_de operator % (string x) {return *this%Bigint_de(x);}
    Bigint_de operator % (ll x)     {return *this%Bigint_de(x);}
      void operator %= (Bigint_de x) {*this = *this%x;}
      void operator %= (string x) {*this = *this%x;}
      void operator %= (ll x)     {*this = *this%x;}
 
    void print() {
        if(sign==-1) putchar('-');
        for(int i=a.size()-1; i>=0; i--) putchar(a[i]);
    }
    friend istream& operator >>(istream &in,Bigint_de &x){
        string s; in>>s; x=s; return in;
    }
    friend ostream& operator <<(ostream &out,Bigint_de &x){
        if(x.sign==-1) putchar('-');
        for(int i=x.size()-1; i>=0; i--)
            putchar(x[i]);
        return out;
    }
    ll toInt(){
        ll num=0;
        for(int i=size()-1;i>=0;i--) num=10LL*num+a[i]-'0';
        return num;
    }
    friend Bigint_de pow(Bigint_de base, Bigint_de pw){
        Bigint_de ans=1;
        while(pw!=0){
            if(pw%2 !=0) ans*=base;
            base*=base, pw/=2;
        }
        return ans;
    }
    friend Bigint_de pow(Bigint_de a, Bigint_de b,Bigint_de mod) {
        if (b==0) return Bigint_de(1);
        Bigint_de tmp=pow(a,b/2,mod);
        if ((b%2)==0) return (tmp*tmp)%mod;
        else return (((tmp*tmp)%mod)*a)%mod;
    }
    friend Bigint_de sqrt(Bigint_de x) {
        Bigint_de ans=x,tmp=(x+1)/2;
        while (tmp<ans) ans=tmp, tmp=(tmp+x/tmp)/2;
        return ans;
    }
    friend Bigint_de gcd(Bigint_de a,Bigint_de b){
        return a%b==0 ? b : gcd(b, a%b);
    }
    friend Bigint_de lcm(Bigint_de a,Bigint_de b){
        return a/gcd(a,b);
    }
};
 
const int MAXN_DE = 350;
const int MAXA_DE = 255;
 
Bigint_de dp_de[MAXN_DE][MAXA_DE];
bool flag_de = false;
 
void calcDP_de() {
    for (int i = 0; i < MAXA_DE; i++) {
        dp_de[0][i] = 1;
    }
    for (int i = 1; i < MAXN_DE; i++) {
        dp_de[i][0] = dp_de[i - 1][0];
        for (int j = 1; j < MAXA_DE; j++) {
            dp_de[i][j] = dp_de[i - 1][j] + dp_de[i][j - 1];
        }
    }
    flag_de = true;
}
 
void decode(int N, int L, int X[]) {
    if (!flag_de) calcDP_de();
    sort(X, X + L);
    Bigint_de pos = 0;
    for (int i = L - 1; i >= 0; i--) {
        for (int j = 0; j < X[i]; j++) pos += dp_de[i][j];
    }
    pos--;
    vector<int> res;
    for (int i = 0; i < N; i++) {
        Bigint_de x = pos % 256;
        res.push_back(x.toInt());
        pos /= 256;
    }
    for (int i = N - 1; i >= 0; i--) {
        output(res[i]);
    }
}

Compilation message (stderr)

encoder.cpp: In member function 'bool Bigint::operator<(Bigint)':
encoder.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
      |            ~~~~~~~~^~~~~~~~~~
encoder.cpp:43:52: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
      |                                       ~~~~~~~~~~~~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'Bigint Bigint::operator+(Bigint)':
encoder.cpp:63:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
      |                               ~^~~~~~~~~
encoder.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (i<a.size()) carry+=a[i]-'0';
      |                 ~^~~~~~~~~
encoder.cpp: In member function 'Bigint Bigint::operator-(Bigint)':
encoder.cpp:84:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i=0,borrow=0; i<a.size(); i++) {
      |                               ~^~~~~~~~~
encoder.cpp: In member function 'Bigint Bigint::operator*(Bigint)':
encoder.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
      |                              ~^~~~~~~~~
encoder.cpp: In member function 'Bigint Bigint::operator/(Bigint)':
encoder.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j=0; j<a.size(); j++) d.a += "0";
      |                      ~^~~~~~~~~

decoder.cpp: In member function 'bool Bigint_de::operator<(Bigint_de)':
decoder.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
      |            ~~~~~~~~^~~~~~~~~~
decoder.cpp:43:52: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
      |                                       ~~~~~~~~~~~~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'Bigint_de Bigint_de::operator+(Bigint_de)':
decoder.cpp:63:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
      |                               ~^~~~~~~~~
decoder.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (i<a.size()) carry+=a[i]-'0';
      |                 ~^~~~~~~~~
decoder.cpp: In member function 'Bigint_de Bigint_de::operator-(Bigint_de)':
decoder.cpp:84:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i=0,borrow=0; i<a.size(); i++) {
      |                               ~^~~~~~~~~
decoder.cpp: In member function 'Bigint_de Bigint_de::operator*(Bigint_de)':
decoder.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
      |                              ~^~~~~~~~~
decoder.cpp: In member function 'Bigint_de Bigint_de::operator/(Bigint_de)':
decoder.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j=0; j<a.size(); j++) d.a += "0";
      |                      ~^~~~~~~~~

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