oj.uz

답안 #153054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153054 2019-09-11T19:31:06 Z qkxwsm 앵무새 (IOI11_parrots) C++14
100 / 100
 979 ms 36104 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 bool asdf = false;

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, MAXN - 1)
	{
		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[])
{
	if (!asdf)
	{
		genchoose();
		asdf = true;
	}
	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;
	}
	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 bool zxcv = false;

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, MAXN - 1)
	{
		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 decode(int n, int m, int a[])
{
	if (!zxcv)
	{
		genchoose();
		zxcv = true;
	}
	FOR(i, 0, 256) freq[i] = 0;
	FOR(i, 0, m) freq[a[i]]++;
	N = n;
	//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 = ad(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:81: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:58:21: warning: 'std::bitset<613> sb(std::bitset<613>&, std::bitset<613>&)' defined but not used [-Wunused-function]
 static bitset<MAXN> sb (bitset<MAXN> &a, bitset<MAXN> &b)
                     ^~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 34984 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 873 ms 35840 KB Output is correct
2 Correct 880 ms 36024 KB Output is correct
3 Correct 895 ms 35704 KB Output is correct
4 Correct 897 ms 35992 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 875 ms 35776 KB Output is correct
2 Correct 885 ms 35880 KB Output is correct
3 Correct 902 ms 35936 KB Output is correct
4 Correct 908 ms 35584 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 892 ms 35760 KB Output is correct
2 Correct 900 ms 35864 KB Output is correct
3 Correct 895 ms 35584 KB Output is correct
4 Correct 908 ms 35824 KB Output is correct
5 Correct 913 ms 35840 KB Output is correct
6 Correct 913 ms 36104 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 895 ms 35768 KB Output is correct - P = 5.000000
2 Correct 917 ms 35896 KB Output is correct - P = 5.000000
3 Correct 925 ms 35824 KB Output is correct - P = 5.000000
4 Correct 957 ms 35992 KB Output is correct - P = 5.000000
5 Correct 974 ms 35912 KB Output is correct - P = 5.000000
6 Correct 977 ms 35824 KB Output is correct - P = 5.000000
7 Correct 979 ms 35976 KB Output is correct - P = 5.000000