| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 575482 | MadokaMagicaFan | Parrots (IOI11_parrots) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
const int N = 64;
const int A = 256;
void send(int a);
void output(int a);
struct bignum {
vector<ll> vals;
ll sz = (1l<<32);
bignum() {vals.pb(0);}
bignum(ll i) {vals.pb(i);}
bignum(const bignum& x) { equal(x); }
int
comp(const bignum& x)
{
int ind1;
int ind2;
for (ind2 = sz(x.vals)-1; ind2 >= 0; --ind2) {
if (x.vals[ind2])
break;
}
for (ind1 = sz(vals)-1; ind1 >= 0; --ind1) {
if (vals[ind1])
break;
}
if (ind1 > ind2)
return 1;
if (ind1 < ind2)
return -1;
while (ind1 > -1) {
if (vals[ind1] > x.vals[ind1])
return 1;
if (vals[ind1] < x.vals[ind1])
return -1;
--ind1;
}
return 0;
}
void
equal(const bignum& x)
{
vals.clear();
for (int i = 0; i < sz(x.vals); ++i)
vals.pb(x.vals[i]);
return;
}
void
setval(int pos, ll val)
{
int blk = pos/4;
while (sz(vals) <= blk)
vals.pb(0);
pos %= 4;
vals[blk] += (val<<(pos*8));
assert(vals[blk] < sz);
}
int
getval(int pos)
{
ll ans;
int blk = pos/4;
if (sz(vals) <= blk)
return 0;
pos %= 4;
ans = vals[blk]>>(pos*8);
ans %= A;
return ans;
}
void
add(const bignum& x)
{
ll reminder = 0;
int ind = 0;
while (ind < sz(x.vals) || reminder) {
if (ind >= sz(vals))
vals.pb(0);
vals[ind] += reminder;
if (ind < sz(x.vals))
vals[ind] += x.vals[ind];
reminder = vals[ind]/sz;
vals[ind] %= sz;
++ind;
}
return;
}
void
add(ll x)
{
ll reminder = x;
int ind = 0;
while (reminder) {
if (ind >= sz(vals))
vals.pb(0);
vals[ind] += reminder;
reminder = vals[ind]/sz;
vals[ind] %= sz;
++ind;
}
return;
}
void
subtr(const bignum& x)
{
assert(this->comp(x) > -1);
ll reminder = 0;
int ind = 0;
while (ind < sz(x.vals) || reminder) {
if (ind >= sz(vals))
assert(0);
vals[ind] -= reminder;
if (ind < sz(x.vals))
vals[ind] -= x.vals[ind];
if (vals[ind] < 0) {
reminder = 0;
while (vals[ind] < 0) {
vals[ind] += sz;
++reminder;
}
} else {
reminder = 0;
}
++ind;
}
return;
}
void
subtr()
{
for (int i = 0; i < sz(vals); ++i) {
if (vals[i]) {
vals[i] -= 1;
break;
}
vals[i] = sz-1;
}
return;
}
void
print()
{
for (int i = sz(vals)-1; i >= 0; --i) {
cout << i << ": " << vals[i] << endl;
}
return;
}
};
bignum dp[5*N][A];
void
init()
{
if (dp[0][1].comp(1)==0)
return;
for (int i = 0; i < A; ++i) {
if(i) {
dp[0][i].equal(dp[0][i-1]);
dp[0][i].add(1);
}
}
for (int i = 1; i < 5*N; ++i) {
for (int j = 0; j < A; ++j) {
if (j)
dp[i][j].equal(dp[i][j-1]);
dp[i][j].add(dp[i-1][j]);
}
}
return;
}
void
encode(int n, int *m)
{
init();
bignum value(0);
for (int i = 0; i < n; ++i) {
value.setval(i,m[i]);
}
if (value.comp(0) == 0) {
send(69);
return;
}
int lb=A-1;
for (int i = n*5-1; i >= 0; --i) {
for (int j = lb; j >= 0; --j) {
if (value.comp(0) == 0)
send(0);
if (value.comp(dp[i][j]) > 0) {
assert(j < A-1);
value.subtr(dp[i][j]);
send(j+1);
lb = j+1;
break;
} else if (!j)
assert(0);
}
}
return;
}
void
decode(int n, int l, int *k)
{
if (l == 1) {
for (int i = 0; i < n; ++i) output(0);
return;
}
init();
assert(l == 5*n);
bignum val(1);
vector<int> s;
for (int i = 0; i < l; ++i) {
s.pb(k[i]);
}
sort(s.begin(), s.end());
for (int i = sz(s)-1; i >= 0; --i) {
if (s[i] == 0)
break;
val.add(dp[i][s[i]-1]);
}
for (int i = 0; i < n; ++i) {
output(val.getval(i));
}
return;
}
#ifdef ONPC
int _a[5*N];
int _m[N];
int _l = 0;
void
send(int a)
{
_a[_l] = a;
++_l;
}
void output(int a)
{
cout << a << ' ';
}
void
solve()
{
int _n;
cin >> _n;
for (int i = 0; i < _n; ++i)
cin >> _m[i];
encode(_n,_m);
cout << _n << endl;
decode(_n,_l,_a);
cout << endl;
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
const int N = 64;
const int A = 256;
void send(int a);
void output(int a);
struct bignum {
vector<ll> vals;
ll sz = (1l<<32);
bignum() {vals.pb(0);}
bignum(ll i) {vals.pb(i);}
bignum(const bignum& x) { equal(x); }
int
comp(const bignum& x)
{
int ind1;
int ind2;
for (ind2 = sz(x.vals)-1; ind2 >= 0; --ind2) {
if (x.vals[ind2])
break;
}
for (ind1 = sz(vals)-1; ind1 >= 0; --ind1) {
if (vals[ind1])
break;
}
if (ind1 > ind2)
return 1;
if (ind1 < ind2)
return -1;
while (ind1 > -1) {
if (vals[ind1] > x.vals[ind1])
return 1;
if (vals[ind1] < x.vals[ind1])
return -1;
--ind1;
}
return 0;
}
void
equal(const bignum& x)
{
vals.clear();
for (int i = 0; i < sz(x.vals); ++i)
vals.pb(x.vals[i]);
return;
}
void
setval(int pos, ll val)
{
int blk = pos/4;
while (sz(vals) <= blk)
vals.pb(0);
pos %= 4;
vals[blk] += (val<<(pos*8));
assert(vals[blk] < sz);
}
int
getval(int pos)
{
ll ans;
int blk = pos/4;
if (sz(vals) <= blk)
return 0;
pos %= 4;
ans = vals[blk]>>(pos*8);
ans %= A;
return ans;
}
void
add(const bignum& x)
{
ll reminder = 0;
int ind = 0;
while (ind < sz(x.vals) || reminder) {
if (ind >= sz(vals))
vals.pb(0);
vals[ind] += reminder;
if (ind < sz(x.vals))
vals[ind] += x.vals[ind];
reminder = vals[ind]/sz;
vals[ind] %= sz;
++ind;
}
return;
}
void
add(ll x)
{
ll reminder = x;
int ind = 0;
while (reminder) {
if (ind >= sz(vals))
vals.pb(0);
vals[ind] += reminder;
reminder = vals[ind]/sz;
vals[ind] %= sz;
++ind;
}
return;
}
void
subtr(const bignum& x)
{
assert(this->comp(x) > -1);
ll reminder = 0;
int ind = 0;
while (ind < sz(x.vals) || reminder) {
if (ind >= sz(vals))
assert(0);
vals[ind] -= reminder;
if (ind < sz(x.vals))
vals[ind] -= x.vals[ind];
if (vals[ind] < 0) {
reminder = 0;
while (vals[ind] < 0) {
vals[ind] += sz;
++reminder;
}
} else {
reminder = 0;
}
++ind;
}
return;
}
void
subtr()
{
for (int i = 0; i < sz(vals); ++i) {
if (vals[i]) {
vals[i] -= 1;
break;
}
vals[i] = sz-1;
}
return;
}
void
print()
{
for (int i = sz(vals)-1; i >= 0; --i) {
cout << i << ": " << vals[i] << endl;
}
return;
}
};
bignum dp[5*N][A];
void
init()
{
if (dp[0][1].comp(1)==0)
return;
for (int i = 0; i < A; ++i) {
if(i) {
dp[0][i].equal(dp[0][i-1]);
dp[0][i].add(1);
}
}
for (int i = 1; i < 5*N; ++i) {
for (int j = 0; j < A; ++j) {
if (j)
dp[i][j].equal(dp[i][j-1]);
dp[i][j].add(dp[i-1][j]);
}
}
return;
}
void
encode(int n, int *m)
{
init();
bignum value(0);
for (int i = 0; i < n; ++i) {
value.setval(i,m[i]);
}
if (value.comp(0) == 0) {
send(69);
return;
}
int lb=A-1;
for (int i = n*5-1; i >= 0; --i) {
for (int j = lb; j >= 0; --j) {
if (value.comp(0) == 0)
send(0);
if (value.comp(dp[i][j]) > 0) {
assert(j < A-1);
value.subtr(dp[i][j]);
send(j+1);
lb = j+1;
break;
} else if (!j)
assert(0);
}
}
return;
}
void
decode(int n, int l, int *k)
{
if (l == 1) {
for (int i = 0; i < n; ++i) output(0);
return;
}
init();
assert(l == 5*n);
bignum val(1);
vector<int> s;
for (int i = 0; i < l; ++i) {
s.pb(k[i]);
}
sort(s.begin(), s.end());
for (int i = sz(s)-1; i >= 0; --i) {
if (s[i] == 0)
break;
val.add(dp[i][s[i]-1]);
}
for (int i = 0; i < n; ++i) {
output(val.getval(i));
}
return;
}
#ifdef ONPC
int _a[5*N];
int _m[N];
int _l = 0;
void
send(int a)
{
_a[_l] = a;
++_l;
}
void output(int a)
{
cout << a << ' ';
}
void
solve()
{
int _n;
cin >> _n;
for (int i = 0; i < _n; ++i)
cin >> _m[i];
encode(_n,_m);
cout << _n << endl;
decode(_n,_l,_a);
cout << endl;
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif