Submission #537939

#TimeUsernameProblemLanguageResultExecution timeMemory
537939DubvasParrots (IOI11_parrots)C++14
100 / 100
1434 ms193656 KiB
#include "encoder.h" #include "encoderlib.h" #define _CRT_SECURE_NO_WARNINGS #include <unordered_map> #include <unordered_set> #include <functional> #include <algorithm> #include <iostream> #include <iomanip> #include <cassert> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <utility> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <random> #include <cmath> #include <deque> #include <queue> #include <stack> #include <ctime> #include <map> #include <set> #/*kek, that works*/pragma GCC optimize("Ofast,unroll-loops,fast-math,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,mmx,abm,popcnt,tune=native") #define all(x) (x).begin(), (x).end() #define an cerr << "-->"; cerr.flush() using namespace std; typedef long long ll; typedef long double ld; const ll inf = (ll)1e18 + 228; const ll cst = (ll)3e1 + 5; const ll mod = (ll)1e9 + 7; const ll maxlog = 25; void ex(ll exitCode = 0) { #ifdef _DEBUG //system("pause"); #endif // _DEBUG exit(exitCode); } const ll base = 1e6; const ll blog = 6; struct bigint { bool is_minus; ll size; ll num[cst]; bigint() { is_minus = 0; size = 0; for (ll i = 0; i < cst; i++) this->num[i] = 0; } bigint(string str) { this->is_minus = 0; reverse(str.begin(), str.end()); for (ll i = 0; i < cst; i++) this->num[i] = 0; ll crr = 1; for (ll i = 0; i < str.size(); i++) { this->num[i / blog] += (str[i] - '0') * crr; crr *= 10; if (crr == base) crr = 1; } this->size = (str.size() + blog - 1) / blog; } bigint& operator=(const bigint& b) { is_minus = b.is_minus; size = b.size; for (ll i = 0; i < cst; i++) num[i] = b[i]; return (*this); } bool operator<(const bigint& that) const { if (this->size != that.size) return this->size < that.size; else { for (ll i = that.size - 1; i >= 0; i--) { if (this->num[i] != that.num[i]) return this->num[i] < that.num[i]; } } return false; } bool operator==(const bigint& that) const { return (!((*this) < (that)) && !((that) < (*this))); } bool operator!=(const bigint& that) const { return !(*this == that); } bool operator>(const bigint& that) const { return that < *this; } ll& operator[](ll q) { if (q >= cst) throw 2; return this->num[q]; } ll operator[](ll q) const { if (q >= cst) throw 2; return this->num[q]; } friend istream& operator>>(istream& src, bigint& dst) { string x; src >> x; dst = bigint(x); return src; } bigint operator+(bigint b) const { ll length = 1 + max(this->size, b.size); for (ll ix = 0; ix < length; ix++) { b.num[ix] += this->num[ix]; b.num[ix + 1] += (b.num[ix] / base); b.num[ix] %= base; } while (b.num[length - 1] == 0 && length > 1) length--; b.size = length; return b; } bigint operator-(const bigint& that) const { const bigint& a = *this; const bigint& b = that; ll carry = 0; bigint c; c = a; for (ll i = 0; i < b.size || carry; i++) { c[i] = a[i] - carry - b[i]; if (c.num[i] < 0) carry = 1, c[i] += base; else carry = 0; } while (c.size > 1 && c[c.size - 1] == 0) { c.size--; } return c; } bigint operator*(const bigint& that) const { bigint c; ll cur = 0; ll carry = 0; for (ll i = 0; i < this->size; i++) { for (ll j = 0; j < that.size || carry; j++) { cur = c[i + j] + carry + (*this)[i] * that[j]; c[i + j] = (cur % base); carry = (cur / base); } } c.size = this->size + that.size + 2; while (c.size > 1 && c[c.size - 1] == 0) c.size--; return c; } bigint operator/(ll that) const { ll carry = 0; ll cur = 0; bigint c; for (ll i = this->size - 1; i >= 0; i--) { cur = (*this)[i] + carry * base; c[i] = cur / that; carry = cur % that; } c.size = this->size; while (c.size > 1 && c[c.size - 1] == 0) c.size--; return c; } ll operator%(const ll b) const { ll carry = 0; ll cur = 0; for (ll i = this->size - 1; i >= 0; i--) { cur = (*this)[i] + carry * base; carry = cur % b; } return carry; } bigint operator/(const bigint& b) const { bigint l("0"); bigint r = (*this) + bigint("1"); bigint m; while (r - l > string("1")) { m = (r + l) / 2; if (m * b > * this) r = m; else l = m; } return l; } bigint operator%(const bigint& b) const { return (*this) - (*this) / b * b; } }; bigint C[576][576]; bigint C_(ll a, ll b) { if (b == 0) return bigint("0"); return C[a + b - 1][b - 1]; } void encode(int n, int vc[]){ C[0][0] = bigint("1"); for (ll i = 1; i <= 575; i++) C[i][i] = C[i][0] = C[0][0]; for (ll i = 2; i <= 575; i++) { for (ll j = 1; j <= min(i - 1, 256ll); j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } ll m = 5 * n; bigint k("0"); for (ll i = n - 1; i >= 0; i--) { for (ll j = 0; j < 8; j++) k = k + k + bigint(to_string((vc[i] >> j) & 1)); } k = k + bigint("1"); for (ll i = 0; i <= 254; i++) { while (C_(m, 255 - i) < k) { k = k - C_(m, 255 - i); send(i); m--; } } while (m--) send(255); }
#include "decoder.h" #include "decoderlib.h" #define _CRT_SECURE_NO_WARNINGS #include <unordered_map> #include <unordered_set> #include <functional> #include <algorithm> #include <iostream> #include <iomanip> #include <cassert> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <utility> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <random> #include <cmath> #include <deque> #include <queue> #include <stack> #include <ctime> #include <map> #include <set> #/*kek, that works*/pragma GCC optimize("Ofast,unroll-loops,fast-math,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,mmx,abm,popcnt,tune=native") #define all(x) (x).begin(), (x).end() #define an cerr << "-->"; cerr.flush() using namespace std; typedef long long ll; typedef long double ld; const ll inf = (ll)1e18 + 228; const ll cst = (ll)3e1 + 5; const ll mod = (ll)1e9 + 7; const ll maxlog = 25; void ex(ll exitCode = 0) { #ifdef _DEBUG //system("pause"); #endif // _DEBUG exit(exitCode); } const ll base = 1e6; const ll blog = 6; struct bigint { bool is_minus; ll size; ll num[cst]; bigint() { is_minus = 0; size = 0; for (ll i = 0; i < cst; i++) this->num[i] = 0; } bigint(string str) { this->is_minus = 0; reverse(str.begin(), str.end()); for (ll i = 0; i < cst; i++) this->num[i] = 0; ll crr = 1; for (ll i = 0; i < str.size(); i++) { this->num[i / blog] += (str[i] - '0') * crr; crr *= 10; if (crr == base) crr = 1; } this->size = (str.size() + blog - 1) / blog; } bigint& operator=(const bigint& b) { is_minus = b.is_minus; size = b.size; for (ll i = 0; i < cst; i++) num[i] = b[i]; return (*this); } bool operator<(const bigint& that) const { if (this->size != that.size) return this->size < that.size; else { for (ll i = that.size - 1; i >= 0; i--) { if (this->num[i] != that.num[i]) return this->num[i] < that.num[i]; } } return false; } bool operator==(const bigint& that) const { return (!((*this) < (that)) && !((that) < (*this))); } bool operator!=(const bigint& that) const { return !(*this == that); } bool operator>(const bigint& that) const { return that < *this; } ll& operator[](ll q) { if (q >= cst) throw 2; return this->num[q]; } ll operator[](ll q) const { if (q >= cst) throw 2; return this->num[q]; } friend istream& operator>>(istream& src, bigint& dst) { string x; src >> x; dst = bigint(x); return src; } bigint operator+(bigint b) const { ll length = 1 + max(this->size, b.size); for (ll ix = 0; ix < length; ix++) { b.num[ix] += this->num[ix]; b.num[ix + 1] += (b.num[ix] / base); b.num[ix] %= base; } while (b.num[length - 1] == 0 && length > 1) length--; b.size = length; return b; } bigint operator-(const bigint& that) const { const bigint& a = *this; const bigint& b = that; ll carry = 0; bigint c; c = a; for (ll i = 0; i < b.size || carry; i++) { c[i] = a[i] - carry - b[i]; if (c.num[i] < 0) carry = 1, c[i] += base; else carry = 0; } while (c.size > 1 && c[c.size - 1] == 0) { c.size--; } return c; } bigint operator*(const bigint& that) const { bigint c; ll cur = 0; ll carry = 0; for (ll i = 0; i < this->size; i++) { for (ll j = 0; j < that.size || carry; j++) { cur = c[i + j] + carry + (*this)[i] * that[j]; c[i + j] = (cur % base); carry = (cur / base); } } c.size = this->size + that.size + 2; while (c.size > 1 && c[c.size - 1] == 0) c.size--; return c; } bigint operator/(ll that) const { ll carry = 0; ll cur = 0; bigint c; for (ll i = this->size - 1; i >= 0; i--) { cur = (*this)[i] + carry * base; c[i] = cur / that; carry = cur % that; } c.size = this->size; while (c.size > 1 && c[c.size - 1] == 0) c.size--; return c; } ll operator%(const ll b) const { ll carry = 0; ll cur = 0; for (ll i = this->size - 1; i >= 0; i--) { cur = (*this)[i] + carry * base; carry = cur % b; } return carry; } bigint operator/(const bigint& b) const { bigint l("0"); bigint r = (*this) + bigint("1"); bigint m; while (r - l > string("1")) { m = (r + l) / 2; if (m * b > * this) r = m; else l = m; } return l; } bigint operator%(const bigint& b) const { return (*this) - (*this) / b * b; } }; bigint C[576][576]; bigint C_(ll a, ll b) { if (b == 0) return bigint("0"); return C[a + b - 1][b - 1]; } void decode(int n, int m, int vc[]){ C[0][0] = bigint("1"); for (ll i = 1; i <= 575; i++) C[i][i] = C[i][0] = C[0][0]; for (ll i = 2; i <= 575; i++) { for (ll j = 1; j <= min(i - 1, 256ll); j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } vector<ll> cnt(256, 0); for (ll i = 0; i < m; i++) cnt[vc[i]]++; bigint k("0"); for (ll i = 0; i <= 255; i++) { while (cnt[i]) { k = k + C_(m, 255 - i); m--; cnt[i]--; } } for (ll i = 0; i < n; i++) { ll curr = 0; for (ll j = 0; j < 8; j++) { curr = 2 * curr + k % 2; k = k / 2; } output(curr); } }

Compilation message (stderr)

encoder.cpp: In constructor 'bigint::bigint(std::string)':
encoder.cpp:70:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (ll i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~

decoder.cpp: In constructor 'bigint::bigint(std::string)':
decoder.cpp:70:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (ll i = 0; i < str.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...