| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537939 |
2022-03-15T22:34:43 Z |
Dubvas |
Parrots (IOI11_parrots) |
C++14 |
|
1434 ms |
193656 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
353 ms |
192904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1427 ms |
193116 KB |
Output is correct |
| 2 |
Correct |
1397 ms |
193296 KB |
Output is correct |
| 3 |
Correct |
1364 ms |
193316 KB |
Output is correct |
| 4 |
Correct |
1352 ms |
193488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1379 ms |
193288 KB |
Output is correct |
| 2 |
Correct |
1370 ms |
193220 KB |
Output is correct |
| 3 |
Correct |
1372 ms |
193392 KB |
Output is correct |
| 4 |
Correct |
1351 ms |
193656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1393 ms |
193276 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
193360 KB |
Output is correct |
| 3 |
Correct |
1365 ms |
193220 KB |
Output is correct |
| 4 |
Correct |
1357 ms |
193368 KB |
Output is correct |
| 5 |
Correct |
1434 ms |
193420 KB |
Output is correct |
| 6 |
Correct |
1354 ms |
193420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1332 ms |
193264 KB |
Output is correct - P = 5.000000 |
| 2 |
Correct |
1377 ms |
193416 KB |
Output is correct - P = 5.000000 |
| 3 |
Correct |
1360 ms |
193428 KB |
Output is correct - P = 5.000000 |
| 4 |
Correct |
1392 ms |
193584 KB |
Output is correct - P = 5.000000 |
| 5 |
Correct |
1411 ms |
193648 KB |
Output is correct - P = 5.000000 |
| 6 |
Correct |
1382 ms |
193544 KB |
Output is correct - P = 5.000000 |
| 7 |
Correct |
1361 ms |
193572 KB |
Output is correct - P = 5.000000 |
