제출 #537938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537938		Dubvas	앵무새 (IOI11_parrots)	C++14	컴파일 에러	0 ms	0 KiB

encoder

#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);
}

decoder

#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 : vc) cnt[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);
	}
}

컴파일 시 표준 에러 (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++) {
      |                  ~~^~~~~~~~~~~~
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:211:15: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
  211 |  for (ll& i : vc) cnt[i]++;
      |               ^~
      |               std::begin
In file included from /usr/include/c++/10/array:41,
                 from /usr/include/c++/10/tuple:39,
                 from /usr/include/c++/10/bits/hashtable_policy.h:34,
                 from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from decoder.cpp:5:
/usr/include/c++/10/bits/range_access.h:108:37: note: 'std::begin' declared here
  108 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
decoder.cpp:211:15: error: 'end' was not declared in this scope; did you mean 'std::end'?
  211 |  for (ll& i : vc) cnt[i]++;
      |               ^~
      |               std::end
In file included from /usr/include/c++/10/array:41,
                 from /usr/include/c++/10/tuple:39,
                 from /usr/include/c++/10/bits/hashtable_policy.h:34,
                 from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from decoder.cpp:5:
/usr/include/c++/10/bits/range_access.h:110:37: note: 'std::end' declared here
  110 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
      |                                     ^~~