Submission #153050

# Submission time Handle Problem Language Result Execution time Memory
153050 2019-09-11T17:59:13 Z qkxwsm Parrots (IOI11_parrots) C++14
0 / 100
487 ms 12040 KB
```#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 613

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

static int N;
static int freq[256];
static bitset<MAXN> bs;
static bitset<MAXN> choose[MAXN][MAXN];

static bitset<MAXN> ad (bitset<MAXN> &a, bitset<MAXN> &b)
{
bool carry = 0;
bitset<MAXN> res;
FOR(i, 0, MAXN - 1)
{
res[i] = a[i] ^ b[i] ^ carry;
if ((a[i] && b[i]) || (b[i] && carry) || (a[i] && carry)) carry = 1;
else carry = 0;
}
return res;
}
static bitset<MAXN> sb (bitset<MAXN> &a, bitset<MAXN> &b)
{
bitset<MAXN> res;
FOR(i, 0, MAXN)
{
res[i] = a[i] ^ b[i];
if (!a[i] && b[i])
{
FOR(j, i + 1, MAXN)
{
if (a[j] == 1)
{
a[j] = 0; break;
}
else
{
a[j] = 1;
}
}
}
}
return res;
}
static int cmp(bitset<MAXN> a, bitset<MAXN> b)
{
//-1 if a < b, 0 if a = b, 1 if a > b
FORD(i, MAXN, 0)
{
if (a[i] && (!b[i])) return 1;
if (b[i] && (!a[i])) return -1;
}
return 0;
}

static void genchoose()
{
choose[0][0][0] = 1;
FOR(i, 1, N + 260)
{
choose[i][0] = choose[0][0];
choose[i][i] = choose[0][0];
FOR(j, 1, i)
{
choose[i][j] = ad(choose[i - 1][j], choose[i - 1][j - 1]);
// if (i <= 10) cerr << i << ' ' << j << ' ' << choose[i][j].to_ullong() << endl;
}
}
}

void encode(int n, int a[])
{
N = n;
//all numbers up to 255
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 8; j++)
{
if (a[i] & (1 << j))
{
bs[8 * i + j] = true;
}
}
}
genchoose();
int rem = 5 * N;
FORD(i, 256, 1)
{
//you have rem places left.
//so if you put 0 then you get x -= 0. if you put 1 you get like (rem - 1 spaces to put 255 #s back.
while(rem > 0)
{
//try putting a space!
//you have i spots left! so you will subtract (i numbers, summing to rem-1) = (rem + i - 2) choose(rem - 1)
bitset<MAXN> cur = choose[rem + i - 2][rem - 1];
if (cmp(cur, bs) == 1) //cur > bs
{
break;
}
else
{
// cerr << "TAKE " << i << endl;
bs = sb(bs, cur);
rem--;
freq[i]++;
}
}
}
freq[0] = rem;
FOR(i, 0, 256)
{
FOR(j, 0, freq[i])
{
// cerr << "SEND " << i << endl;
send(i);
}
// if (freq[i] != 0)
// {
// 	cerr << "SEND " << i << ' ' << freq[i] << "x" << endl;
// }
}
//it's like a sequence:
//you have a bit sequence, and you want to convert it to a sum(xi) = 5N

}
```
```#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 613

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

static int N;
static int freq[256];
static bitset<MAXN> choose[MAXN][MAXN];
static bitset<MAXN> bs;
static int ans[MAXN];

static bitset<MAXN> operator + (bitset<MAXN> &a, bitset<MAXN> &b)
{
bool carry = 0;
bitset<MAXN> res;
FOR(i, 0, MAXN - 1)
{
res[i] = a[i] ^ b[i] ^ carry;
if ((a[i] && b[i]) || (b[i] && carry) || (a[i] && carry)) carry = 1;
else carry = 0;
}
return res;
}
static bitset<MAXN> operator - (bitset<MAXN> &a, bitset<MAXN> &b)
{
bitset<MAXN> res;
FOR(i, 0, MAXN)
{
res[i] = a[i] ^ b[i];
if (!a[i] && b[i])
{
FOR(j, i + 1, MAXN)
{
if (a[j] == 1)
{
a[j] = 0; break;
}
else
{
a[j] = 1;
}
}
}
}
return res;
}
static int cmp(bitset<MAXN> a, bitset<MAXN> b)
{
//-1 if a < b, 0 if a = b, 1 if a > b
FORD(i, MAXN, 0)
{
if (a[i] && (!b[i])) return 1;
if (b[i] && (!a[i])) return -1;
}
return 0;
}
static void genchoose()
{
choose[0][0][0] = 1;
FOR(i, 1, N + 260)
{
choose[i][0] = choose[0][0];
choose[i][i] = choose[0][0];
FOR(j, 1, i)
{
choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];
}
}
}

void decode(int n, int m, int a[])
{
FOR(i, 0, m) freq[a[i]]++;
N = n;
genchoose();
//so you received a set of bits.
int rem = 5 * N;
FORD(i, 256, 1)
{
int x = freq[i];
while(x--)
{
//you have i numbers, and they sum to rem-1
bs = bs + choose[rem + i - 2][rem - 1];
rem--;
}
}
FOR(i, 0, N)
{
ans[i] = 0;
FOR(j, 0, 8)
{
if (bs[8 * i + j])
{
ans[i] += (1 << j);
}
}
}
// cerr << "ANS";
FOR(i, 0, N)
{
// cerr << ' ' << ans[i];
output(ans[i]);
}
// cerr << endl;
}
```

Compilation message

```decoder.cpp:80:12: warning: 'int cmp(std::bitset<613>, std::bitset<613>)' defined but not used [-Wunused-function]
static int cmp(bitset<MAXN> a, bitset<MAXN> b)
^~~
decoder.cpp:57:21: warning: 'std::bitset<613> operator-(std::bitset<613>&, std::bitset<613>&)' defined but not used [-Wunused-function]
static bitset<MAXN> operator - (bitset<MAXN> &a, bitset<MAXN> &b)
^~~~~~~~```

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 8688 KB Error : Encoded message too long

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 8648 KB Error : Encoded message too long
2 Halted 0 ms 0 KB -

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 8640 KB Error : Encoded message too long
2 Halted 0 ms 0 KB -

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 8624 KB Error : Encoded message too long
2 Halted 0 ms 0 KB -