답안 #153051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153051 2019-09-11T18:07:20 Z qkxwsm 앵무새 (IOI11_parrots) C++14
17 / 100
2000 ms 9044 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;
			}
		}
	}
	FOR(i, 0, 256)
	{
		freq[i] = 0;
	}
	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, 256) freq[i] = 0;
	FOR(i, 0, m) freq[a[i]]++;
	N = n;
	genchoose();
	//so you received a set of bits.
	int rem = 5 * N;
	bs.reset();
	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)
                     ^~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1596 ms 9044 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2058 ms 4604 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2067 ms 4524 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2062 ms 4460 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2032 ms 4984 KB Time limit exceeded
2 Execution timed out 2063 ms 5176 KB Time limit exceeded
3 Execution timed out 2063 ms 5348 KB Time limit exceeded
4 Execution timed out 2066 ms 5756 KB Time limit exceeded
5 Execution timed out 2054 ms 6036 KB Time limit exceeded
6 Execution timed out 2062 ms 6264 KB Time limit exceeded
7 Execution timed out 2049 ms 6340 KB Time limit exceeded