oj.uz

Submission #105388

# Submission time Handle Problem Language Result Execution time Memory
105388 2019-04-11T18:21:31 Z eriksuenderhauf Parrots (IOI11_parrots) C++11
100 / 100
 504 ms 232952 KB 
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
//#include "grader.h"
using namespace std;

struct bigInt
{
	const int sz = 80;
	int val[81];

	bigInt() {
		memset(val, 0, sizeof val);
	}

	bigInt &operator += (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] += rhs.val[i];
			val[i + 1] += (val[i] >> 8);
			val[i] &= 255;
		}
		return *this;
	}

	bigInt &operator -= (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] -= rhs.val[i];
			if (val[i] < 0) {
				val[i + 1]--;
				val[i] += 256;
			}
		}
		return *this;
	}

	bool operator <= (const bigInt &rhs) {
		for (int i = sz - 1; i > -1; i--) {
			if (val[i] < rhs.val[i]) return 1;
			if (val[i] > rhs.val[i]) return 0;
		}
		return 1;
	}
};

static bigInt operator +(const bigInt lhs, const bigInt rhs) {
	bigInt ret;
	ret += lhs;
	ret += rhs;
	return ret;
}

static int a[800], cnt[300];
static bigInt dp[600][600];
static bool init = 1;

void encode(int n, int M[]) {
	if (init) {
		dp[0][0].val[0] = 1;
		for (int i = 1; i < 600; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i)
					dp[i][j].val[0] = 1;
				else
					dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1];
			}
		}
		init = 0;
	}
	memset(cnt, 0, sizeof cnt);
	bigInt cur;
	for (int i = 0; i < n; i++)
		cur.val[i] = M[i];
	int len = 5 * n;
	for (int i = 0; i < 256; i++) {
		while (dp[255 - i + len][len] <= cur) {
			cur -= dp[255 - i + len][len];
			len--;
			cnt[i]++;
		}
	}
	for (int j = 0; j < 256; j++)
		while (cnt[j]--)
			send(j);
}
#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
//#include "grader.h"
static int a[800], b[800];
static int val[16] = {0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0};

struct bigInt
{
	const int sz = 80;
	int val[81];

	bigInt() {
		memset(val, 0, sizeof val);
	}

	bigInt &operator += (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] += rhs.val[i];
			val[i + 1] += (val[i] >> 8);
			val[i] &= 255;
		}
		return *this;
	}

	bigInt &operator -= (const bigInt &rhs) {
		for (int i = 0; i < sz; i++) {
			val[i] -= rhs.val[i];
			if (val[i] < 0) {
				val[i + 1]--;
				val[i] += 256;
			}
		}
		return *this;
	}

	bool operator <= (const bigInt &rhs) {
		for (int i = sz - 1; i > -1; i--) {
			if (val[i] < rhs.val[i]) return 1;
			if (val[i] > rhs.val[i]) return 0;
		}
		return 1;
	}
};

static bigInt operator +(const bigInt lhs, const bigInt rhs) {
	bigInt ret;
	ret += lhs;
	ret += rhs;
	return ret;
}

static bigInt dp[600][600];
static bool init = 1;

void decode(int n, int L, int X[]) {
	if (init) {
		dp[0][0].val[0] = 1;
		for (int i = 1; i < 600; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i)
					dp[i][j].val[0] = 1;
				else
					dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1];
			}
		}
		init = 0;
	}
	bigInt cur;
	std::sort(X, X + L);
	int len = 5 * n - L;
	for (int i = L - 1; i > -1; i--) {
		int j = i;
		while (j > -1 && X[j] == X[i]) {
			len++; j--;
			cur += dp[255 - X[i] + len][len];
		}
		i = j + 1;
	}
	for (int i = 0; i < n; i++)
		output(cur.val[i]);
}

Compilation message

encoder.cpp:52:12: warning: 'a' defined but not used [-Wunused-variable]
 static int a[800], cnt[300];
            ^

decoder.cpp:6:12: warning: 'val' defined but not used [-Wunused-variable]
 static int val[16] = {0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0};
            ^~~
decoder.cpp:5:20: warning: 'b' defined but not used [-Wunused-variable]
 static int a[800], b[800];
                    ^
decoder.cpp:5:12: warning: 'a' defined but not used [-Wunused-variable]
 static int a[800], b[800];
            ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 232008 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 232432 KB Output is correct
2 Correct 460 ms 232688 KB Output is correct
3 Correct 501 ms 232688 KB Output is correct
4 Correct 451 ms 232688 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 232632 KB Output is correct
2 Correct 486 ms 232632 KB Output is correct
3 Correct 487 ms 232624 KB Output is correct
4 Correct 479 ms 232688 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 232816 KB Output is correct
2 Correct 473 ms 232672 KB Output is correct
3 Correct 489 ms 232712 KB Output is correct
4 Correct 491 ms 232816 KB Output is correct
5 Correct 483 ms 232688 KB Output is correct
6 Correct 490 ms 232688 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 232632 KB Output is correct - P = 5.000000
2 Correct 484 ms 232624 KB Output is correct - P = 5.000000
3 Correct 504 ms 232688 KB Output is correct - P = 5.000000
4 Correct 472 ms 232688 KB Output is correct - P = 5.000000
5 Correct 482 ms 232952 KB Output is correct - P = 5.000000
6 Correct 478 ms 232944 KB Output is correct - P = 5.000000
7 Correct 463 ms 232888 KB Output is correct - P = 5.000000