제출 #433327

#제출 시각아이디문제언어결과실행 시간메모리
433327quickn앵무새 (IOI11_parrots)C++14
17 / 100
2084 ms16432 KiB
#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); } }
#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); } }

컴파일 시 표준 에러 (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++) {
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...