| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 58669 | kingpig9 | Parrots (IOI11_parrots) | C++11 | 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.
//START COPY
#include <bits/stdc++.h>
#include "encoder.h"
using namespace std;
typedef bitset<576> bset;
static void operator += (bset &b1, bset b2) {
bool carry = 0;
for (int i = 0; i < 576; i++) {
int x = int(b1[i]) + int(b2[i]) + carry;
b1[i] = bool(x & 1);
carry = (x >= 2);
}
}
static void operator -= (bset &b1, bset b2) {
//b1 + (~b2) + 1
//optimize the +1
for (int i = 0; i < 576; i++) {
if (!b1[i]) {
b1[i] = true;
for (int j = 0; j < i; j++) {
b1[j] = false;
}
break;
}
}
b1 += (~b2);
}
static bset operator + (bset b1, bset b2) {
b1 += b2;
return b1;
}
static bset operator - (bset b1, bset b2) {
b1 -= b2;
return b1;
}
static bool operator < (bset b1, bset b2) {
for (int i = 575; i >= 0; i--) {
if (b1[i] < b2[i]) {
return true;
}
if (b1[i] > b2[i]) {
return false;
}
}
return false;
}
static bool operator >= (bset b1, bset b2) {
return !(b1 < b2);
}
static bool operator > (bset b1, bset b2) {
return b2 < b1;
}
static bool operator <= (bset b1, bset b2) {
return !(b2 < b1);
}
static bset cho[576][256];
static void precomp() {
for (int i = 0; i < 576; i++) {
cho[i][0][0] = 1;
for (int j = 1; j <= i && j < 256; j++) {
cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
}
}
}
static bset nsum (int n, int s) {
return cho[n + s - 1][n - 1];
}
static int N;
static int K;
//END COPY
void encode (int nn, int mm[]) {
N = nn;
K = 5 * N;
precomp();
//ok let's go!
bset rnk = bset();
for (int i = 0; i < N; i++) {
rnk |= (bset(mm[i]) << (8 * i));
}
//ok now get this number rank
vector<int> ans;
for (int i = 0; i < K; i++) {
//if you put this one then what will you get?
int prv = (ans.empty() ? 0 : ans.back());
for (int j = prv; j < 256; j++) {
//test if next one is > j.
//if not then choose this one and break
bset nways = nsum(256 - j, K - 1 - i);
if (rnk >= nways) {
rnk -= nways;
} else {
ans.push_back(j);
break;
}
}
}
//printf("SEND:");
for (int x : ans) {
//printf(" %d", x);
send(x);
}
//printf("\n");
}
//START COPY
#include <bits/stdc++.h>
#include "decoder.h"
using namespace std;
typedef bitset<576> bset;
static void operator += (bset &b1, bset b2) {
bool carry = 0;
for (int i = 0; i < 576; i++) {
int x = int(b1[i]) + int(b2[i]) + carry;
b1[i] = bool(x & 1);
carry = (x >= 2);
}
}
static void operator -= (bset &b1, bset b2) {
//b1 + (~b2) + 1
//optimize the +1
for (int i = 0; i < 576; i++) {
if (!b1[i]) {
b1[i] = true;
for (int j = 0; j < i; j++) {
b1[j] = false;
}
break;
}
}
b1 += (~b2);
}
static bset operator + (bset b1, bset b2) {
b1 += b2;
return b1;
}
static bset operator - (bset b1, bset b2) {
b1 -= b2;
return b1;
}
static bool operator < (bset b1, bset b2) {
for (int i = 575; i >= 0; i--) {
if (b1[i] < b2[i]) {
return true;
}
if (b1[i] > b2[i]) {
return false;
}
}
return false;
}
static bool operator >= (bset b1, bset b2) {
return !(b1 < b2);
}
static bool operator > (bset b1, bset b2) {
return b2 < b1;
}
static bool operator <= (bset b1, bset b2) {
return !(b2 < b1);
}
static bset cho[576][256];
static void precomp() {
for (int i = 0; i < 576; i++) {
cho[i][0][0] = 1;
for (int j = 1; j <= i && j < 256; j++) {
cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
}
}
}
static bset nsum (int n, int s) {
return cho[n + s - 1][n - 1];
}
static int N;
static int K;
//END COPY
void decode (int nn, int kk, int X[]) {
N = nn;
K = kk;
precomp();
//find the rank of this one
bset rnk = bset();
for (int i = 0; i < K; i++) {
int prv = (i == 0 ? 0 : X[i - 1]);
for (int j = prv; j < X[i]; j++) {
//add this amount of stuff
bset nways = nsum(256 - j, K - 1 - i);
rnk += nways;
}
}
//printf("OUTPUT:");
for (int i = 0; i < N; i++) {
//ok let's do this
int val = (rnk & bset(255)).to_ulong();
//printf(" %d", val);
output(val);
rnk >>= 8;
}
//printf("\n");
}