제출 #537939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537939		Dubvas	앵무새 (IOI11_parrots)	C++14	100 / 100	1434 ms	193656 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 = 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);
	}
}

컴파일 시 표준 에러 (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++) {
      |                  ~~^~~~~~~~~~~~

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