Submission #433327

#	Time	Username	Problem	Language	Result	Execution time	Memory
433327		quickn	Parrots (IOI11_parrots)	C++14	17 / 100	2084 ms	16432 KiB

encoder

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

/* https://github.com/williamchanrico/biginteger-cpp/blob/master/BigInt.cpp */
class BigInt {
public:
    int sign;
    string s;

    BigInt()
        : s("")
    {
    }

    BigInt(string x)
    {
        *this = x;
    }

    BigInt(int x)
    {
        *this = to_string(x);
    }

    BigInt negative()
    {
        BigInt x = *this;

        x.sign *= -1;

        return x;
    }

    BigInt normalize(int newSign)
    {
        for (int a = s.size() - 1; a > 0 && s[a] == '0'; a--)
            s.erase(s.begin() + a);

        sign = (s.size() == 1 && s[0] == '0' ? 1 : newSign);

        return *this;
    }

    void operator=(string x)
    {
        int newSign = (x[0] == '-' ? -1 : 1);

        s = (newSign == -1 ? x.substr(1) : x);

        reverse(s.begin(), s.end());

        this->normalize(newSign);
    }

    bool operator==(const BigInt& x) const
    {
        return (s == x.s && sign == x.sign);
    }

    bool operator<(const BigInt& x) const
    {
        if (sign != x.sign)
            return sign < x.sign;

        if (s.size() != x.s.size())
            return (sign == 1 ? s.size() < x.s.size() : s.size() > x.s.size());

        for (int a = s.size() - 1; a >= 0; a--)
            if (s[a] != x.s[a])
                return (sign == 1 ? s[a] < x.s[a] : s[a] > x.s[a]);

        return false;
    }

    bool operator<=(const BigInt& x) const
    {
        return (*this < x || *this == x);
    }

    bool operator>(const BigInt& x) const
    {
        return (!(*this < x) && !(*this == x));
    }

    bool operator>=(const BigInt& x) const
    {
        return (*this > x || *this == x);
    }

    BigInt operator+(BigInt x)
    {
        BigInt curr = *this;

        if (curr.sign != x.sign)
            return curr - x.negative();

        BigInt res;

        for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
            carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);

            res.s += (carry % 10 + '0');

            carry /= 10;
        }

        return res.normalize(sign);
    }

    BigInt operator-(BigInt x)
    {
        BigInt curr = *this;

        if (curr.sign != x.sign)
            return curr + x.negative();

        int realSign = curr.sign;

        curr.sign = x.sign = 1;

        if (curr < x)
            return ((x - curr).negative()).normalize(-realSign);

        BigInt res;

        for (int a = 0, borrow = 0; a < s.size(); a++) {
            borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));

            res.s += (borrow >= 0 ? borrow + '0' : borrow + '0' + 10);

            borrow = (borrow >= 0 ? 0 : 1);
        }

        return res.normalize(realSign);
    }

    BigInt operator*(BigInt x)
    {
        BigInt res("0");

        for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
            while (b--)
                res = (res + x);

            x.s.insert(x.s.begin(), '0');
        }

        return res.normalize(sign * x.sign);
    }

    BigInt operator/(BigInt x)
    {
        if (x.s.size() == 1 && x.s[0] == '0')
            x.s[0] /= (x.s[0] - '0');

        BigInt temp("0"), res;

        for (int a = 0; a < s.size(); a++)
            res.s += "0";

        int newSign = sign * x.sign;

        x.sign = 1;

        for (int a = s.size() - 1; a >= 0; a--) {
            temp.s.insert(temp.s.begin(), '0');
            temp = temp + s.substr(a, 1);

            while (!(temp < x)) {
                temp = temp - x;
                res.s[a]++;
            }
        }

        return res.normalize(newSign);
    }

    BigInt operator%(BigInt x)
    {
        if (x.s.size() == 1 && x.s[0] == '0')
            x.s[0] /= (x.s[0] - '0');

        BigInt res("0");

        x.sign = 1;

        for (int a = s.size() - 1; a >= 0; a--) {
            res.s.insert(res.s.begin(), '0');

            res = res + s.substr(a, 1);

            while (!(res < x))
                res = res - x;
        }

        return res.normalize(sign);
    }

    // operator string(){
    // 	string ret = s;

    // 	reverse(ret.begin(), ret.end());

    // 	return (sign == -1 ? "-" : "") + s;
    // }

    string toString() const
    {
        string ret = s;

        reverse(ret.begin(), ret.end());

        return (sign == -1 ? "-" : "") + ret;
    }

    BigInt toBase10(int base)
    {
        BigInt exp(1), res("0"), BASE(base);

        for (int a = 0; a < s.size(); a++) {
            int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

            res = res + (exp * BigInt(curr));
            exp = exp * BASE;
        }

        return res.normalize(sign);
    }

    BigInt toBase10(int base, BigInt mod)
    {
        BigInt exp(1), res("0"), BASE(base);

        for (int a = 0; a < s.size(); a++) {
            int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

            res = (res + ((exp * BigInt(curr) % mod)) % mod);
            exp = ((exp * BASE) % mod);
        }

        return res.normalize(sign);
    }

    string convertToBase(int base)
    {
        BigInt ZERO(0), BASE(base), x = *this;
        string modes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        if (x == ZERO)
            return "0";

        string res = "";

        while (x > ZERO) {
            BigInt mod = x % BASE;

            x = x - mod;

            if (x > ZERO)
                x = x / BASE;

            res = modes[stoi(mod.toString())] + res;
        }

        return res;
    }

    BigInt toBase(int base)
    {
        return BigInt(this->convertToBase(base));
    }

    friend ostream& operator<<(ostream& os, const BigInt& x)
    {
        os << x.toString();

        return os;
    }
};

typedef unsigned long long i64;

const int MAX = 263;

void encode(int N, int M[]) {
    vector<pair<int, int>> list(N, make_pair(0, 0));
	for (int i = 0; i < N; i++) {
        list[i] = make_pair(M[i], i);
    }
    BigInt msg = 0;
    for (int j = 0; j < N; j++) {
        msg = msg*BigInt(256) + BigInt(list[N-j-1].first);
    }
    BigInt msg2 = 0;
    for (int j = 0; j < 64; j++) {
        msg2 = msg2*BigInt(256) + BigInt(255);
    }
    vector<vector<BigInt>> dp(MAX, vector<BigInt>(256, BigInt(0)));
    for (int j = 0; j < 256; j++)
        dp[0][j] = BigInt(1);
    for (int i = 1; i < MAX; i++) {
        for (int j = 0; j < 256; j++)
            if (j > 0)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            else
                dp[i][j] = dp[i-1][j];
    }
    BigInt m = msg;
    int i = min(262, 4*N);
    int j = 255;
    vector<int> arr;
    while (i >= 0) {
        bool non = false;
        while (m > 0 && j > 0) {
            if (dp[i][j-1] == m) {
                m = m - dp[i][j-1];
                arr.push_back(j);
                non = true;
                break;
            } else if (dp[i][j-1] < m) {
                m = m - dp[i][j-1];
                arr.push_back(j+1);
                non = true;
                break;
            }
            j--;
        }
        if (!non) { arr.push_back(0); }
        i--;
    }
    for (auto a: arr) {
        send(a);
    }
}

decoder

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

/* https://github.com/williamchanrico/biginteger-cpp/blob/master/BigInt.cpp */
class BigInt {
public:
    int sign;
    string s;

    BigInt()
        : s("")
    {
    }

    BigInt(string x)
    {
        *this = x;
    }

    BigInt(int x)
    {
        *this = to_string(x);
    }

    BigInt negative()
    {
        BigInt x = *this;

        x.sign *= -1;

        return x;
    }

    BigInt normalize(int newSign)
    {
        for (int a = s.size() - 1; a > 0 && s[a] == '0'; a--)
            s.erase(s.begin() + a);

        sign = (s.size() == 1 && s[0] == '0' ? 1 : newSign);

        return *this;
    }

    void operator=(string x)
    {
        int newSign = (x[0] == '-' ? -1 : 1);

        s = (newSign == -1 ? x.substr(1) : x);

        reverse(s.begin(), s.end());

        this->normalize(newSign);
    }

    bool operator==(const BigInt& x) const
    {
        return (s == x.s && sign == x.sign);
    }

    bool operator<(const BigInt& x) const
    {
        if (sign != x.sign)
            return sign < x.sign;

        if (s.size() != x.s.size())
            return (sign == 1 ? s.size() < x.s.size() : s.size() > x.s.size());

        for (int a = s.size() - 1; a >= 0; a--)
            if (s[a] != x.s[a])
                return (sign == 1 ? s[a] < x.s[a] : s[a] > x.s[a]);

        return false;
    }

    bool operator<=(const BigInt& x) const
    {
        return (*this < x || *this == x);
    }

    bool operator>(const BigInt& x) const
    {
        return (!(*this < x) && !(*this == x));
    }

    bool operator>=(const BigInt& x) const
    {
        return (*this > x || *this == x);
    }

    BigInt operator+(BigInt x)
    {
        BigInt curr = *this;

        if (curr.sign != x.sign)
            return curr - x.negative();

        BigInt res;

        for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
            carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);

            res.s += (carry % 10 + '0');

            carry /= 10;
        }

        return res.normalize(sign);
    }

    BigInt operator-(BigInt x)
    {
        BigInt curr = *this;

        if (curr.sign != x.sign)
            return curr + x.negative();

        int realSign = curr.sign;

        curr.sign = x.sign = 1;

        if (curr < x)
            return ((x - curr).negative()).normalize(-realSign);

        BigInt res;

        for (int a = 0, borrow = 0; a < s.size(); a++) {
            borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));

            res.s += (borrow >= 0 ? borrow + '0' : borrow + '0' + 10);

            borrow = (borrow >= 0 ? 0 : 1);
        }

        return res.normalize(realSign);
    }

    BigInt operator*(BigInt x)
    {
        BigInt res("0");

        for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
            while (b--)
                res = (res + x);

            x.s.insert(x.s.begin(), '0');
        }

        return res.normalize(sign * x.sign);
    }

    BigInt operator/(BigInt x)
    {
        if (x.s.size() == 1 && x.s[0] == '0')
            x.s[0] /= (x.s[0] - '0');

        BigInt temp("0"), res;

        for (int a = 0; a < s.size(); a++)
            res.s += "0";

        int newSign = sign * x.sign;

        x.sign = 1;

        for (int a = s.size() - 1; a >= 0; a--) {
            temp.s.insert(temp.s.begin(), '0');
            temp = temp + s.substr(a, 1);

            while (!(temp < x)) {
                temp = temp - x;
                res.s[a]++;
            }
        }

        return res.normalize(newSign);
    }

    BigInt operator%(BigInt x)
    {
        if (x.s.size() == 1 && x.s[0] == '0')
            x.s[0] /= (x.s[0] - '0');

        BigInt res("0");

        x.sign = 1;

        for (int a = s.size() - 1; a >= 0; a--) {
            res.s.insert(res.s.begin(), '0');

            res = res + s.substr(a, 1);

            while (!(res < x))
                res = res - x;
        }

        return res.normalize(sign);
    }

    // operator string(){
    // 	string ret = s;

    // 	reverse(ret.begin(), ret.end());

    // 	return (sign == -1 ? "-" : "") + s;
    // }

    string toString() const
    {
        string ret = s;

        reverse(ret.begin(), ret.end());

        return (sign == -1 ? "-" : "") + ret;
    }

    BigInt toBase10(int base)
    {
        BigInt exp(1), res("0"), BASE(base);

        for (int a = 0; a < s.size(); a++) {
            int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

            res = res + (exp * BigInt(curr));
            exp = exp * BASE;
        }

        return res.normalize(sign);
    }

    BigInt toBase10(int base, BigInt mod)
    {
        BigInt exp(1), res("0"), BASE(base);

        for (int a = 0; a < s.size(); a++) {
            int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));

            res = (res + ((exp * BigInt(curr) % mod)) % mod);
            exp = ((exp * BASE) % mod);
        }

        return res.normalize(sign);
    }

    string convertToBase(int base)
    {
        BigInt ZERO(0), BASE(base), x = *this;
        string modes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        if (x == ZERO)
            return "0";

        string res = "";

        while (x > ZERO) {
            BigInt mod = x % BASE;

            x = x - mod;

            if (x > ZERO)
                x = x / BASE;

            res = modes[stoi(mod.toString())] + res;
        }

        return res;
    }

    BigInt toBase(int base)
    {
        return BigInt(this->convertToBase(base));
    }

    friend ostream& operator<<(ostream& os, const BigInt& x)
    {
        os << x.toString();

        return os;
    }
};

typedef unsigned long long i64;

const int MAX = 263;

void decode(int N, int L, int X[]) {
    vector<vector<BigInt>> dp(MAX, vector<BigInt>(256, BigInt(0)));
    for (int j = 0; j < 256; j++)
        dp[0][j] = BigInt(1);
    for (int i = 1; i < MAX; i++) {
        for (int j = 0; j < 256; j++)
            if (j > 0)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            else
                dp[i][j] = dp[i-1][j];
    }
    vector<int> arr;
    for (int i = 0; i < L; i++)
        arr.push_back(X[i]);
    sort(arr.begin(), arr.end(), greater<int>());
    BigInt nth = BigInt(0);
    for (int i = 0; i < L; i++) {
        if (arr[i] == 0)
            break;
        if (i == L-1 || arr[i+1] == 0) {
            nth = nth + dp[L-i-1][arr[i]-1];
        } else {
            nth = nth + dp[L-i-1][arr[i]-2];
        }
    }
    for (int i = 0; i < N; i++) {
        string s = (nth % BigInt(256)).convertToBase(10);
        int n_i = 0;
        for (int i = 0; i < s.size(); i++) {
            n_i *= 10;
            n_i += (s[i] - '0');
        }
        output(n_i);
        nth = nth / BigInt(256);
    }
}

Compilation message (stderr)

encoder.cpp: In member function 'BigInt BigInt::operator+(BigInt)':
encoder.cpp:104:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
      |                                    ~~^~~~~~~~~~
encoder.cpp:104:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
      |                                                    ~~^~~~~~~~~~~~
encoder.cpp:105:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |                       ~~^~~~~~~~~~~~~~~
encoder.cpp:105:69: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |                                                                   ~~^~~~~~~~~~~~
encoder.cpp: In member function 'BigInt BigInt::operator-(BigInt)':
encoder.cpp:131:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (int a = 0, borrow = 0; a < s.size(); a++) {
      |                                     ~~^~~~~~~~~~
encoder.cpp:132:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
      |                                             ~~^~~~~~~~~~~~
encoder.cpp: In member function 'BigInt BigInt::operator*(BigInt)':
encoder.cpp:146:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
      |                                         ~~^~~~~~~~~~
encoder.cpp: In member function 'BigInt BigInt::operator/(BigInt)':
encoder.cpp:163:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for (int a = 0; a < s.size(); a++)
      |                         ~~^~~~~~~~~~
encoder.cpp: In member function 'BigInt BigInt::toBase10(int)':
encoder.cpp:225:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         for (int a = 0; a < s.size(); a++) {
      |                         ~~^~~~~~~~~~
encoder.cpp: In member function 'BigInt BigInt::toBase10(int, BigInt)':
encoder.cpp:239:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         for (int a = 0; a < s.size(); a++) {
      |                         ~~^~~~~~~~~~

decoder.cpp: In member function 'BigInt BigInt::operator+(BigInt)':
decoder.cpp:104:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
      |                                    ~~^~~~~~~~~~
decoder.cpp:104:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
      |                                                    ~~^~~~~~~~~~~~
decoder.cpp:105:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |                       ~~^~~~~~~~~~~~~~~
decoder.cpp:105:69: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
      |                                                                   ~~^~~~~~~~~~~~
decoder.cpp: In member function 'BigInt BigInt::operator-(BigInt)':
decoder.cpp:131:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (int a = 0, borrow = 0; a < s.size(); a++) {
      |                                     ~~^~~~~~~~~~
decoder.cpp:132:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
      |                                             ~~^~~~~~~~~~~~
decoder.cpp: In member function 'BigInt BigInt::operator*(BigInt)':
decoder.cpp:146:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
      |                                         ~~^~~~~~~~~~
decoder.cpp: In member function 'BigInt BigInt::operator/(BigInt)':
decoder.cpp:163:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for (int a = 0; a < s.size(); a++)
      |                         ~~^~~~~~~~~~
decoder.cpp: In member function 'BigInt BigInt::toBase10(int)':
decoder.cpp:225:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         for (int a = 0; a < s.size(); a++) {
      |                         ~~^~~~~~~~~~
decoder.cpp: In member function 'BigInt BigInt::toBase10(int, BigInt)':
decoder.cpp:239:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         for (int a = 0; a < s.size(); a++) {
      |                         ~~^~~~~~~~~~
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:318:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  318 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~

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