oj.uz

Submission #58674

# Submission time Handle Problem Language Result Execution time Memory
58674 2018-07-18T18:58:08 Z kingpig9 Parrots (IOI11_parrots) C++11
100 / 100
 816 ms 23712 KB 
//START COPY

#include <bits/stdc++.h>
#include "encoderlib.h"

using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct bigint1 {
	unsigned arr[18];

	bigint1() {
		fillchar(arr, 0);
	}

	bigint1 (int x) {
		fillchar(arr, 0);
		arr[0] = x;
	}
};

static void operator += (bigint1 &b1, bigint1 b2) {
	bool carry = 0;
	for (int i = 0; i < 18; i++) {
		ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
		b1.arr[i] = x;
		carry = (x >= (1ll << 32));
	}
}

static void operator -= (bigint1 &b1, bigint1 b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 18; i++) {
		b2.arr[i] = ~b2.arr[i];
	}
	b1 += b2;
	b1 += bigint1(1);
}

static bigint1 operator + (bigint1 b1, bigint1 b2) {
	b1 += b2;
	return b1;
}

static bigint1 operator - (bigint1 b1, bigint1 b2) {
	b1 -= b2;
	return b1;
}

static bool operator < (bigint1 b1, bigint1 b2) {
	for (int i = 17; i >= 0; i--) {
		if (b1.arr[i] < b2.arr[i]) {
			return true;
		}
		if (b1.arr[i] > b2.arr[i]) {
			return false;
		}
	}
	return false;
}

static bool operator >= (bigint1 b1, bigint1 b2) {
	return !(b1 < b2);
}

static bool operator > (bigint1 b1, bigint1 b2) {
	return b2 < b1;
}

static bool operator <= (bigint1 b1, bigint1 b2) {
	return !(b2 < b1);
}

static const int MAXV = 5 * 64 + 256;
static bigint1 cho[MAXV][256];
static void precomp() {
	for (int i = 0; i < MAXV; i++) {
		cho[i][0].arr[0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bigint1 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!
	bigint1 rnk = bigint1();
	for (int i = 0; i < N; i++) {
		rnk.arr[i / 4] |= (mm[i] << (8 * (i % 4)));
	}

	//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
			bigint1 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 "decoderlib.h"

using namespace std;
typedef long long ll;
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct bigint2 {
	unsigned arr[18];

	bigint2() {
		fillchar(arr, 0);
	}

	bigint2 (int x) {
		fillchar(arr, 0);
		arr[0] = x;
	}
};

static void operator += (bigint2 &b1, bigint2 b2) {
	bool carry = 0;
	for (int i = 0; i < 18; i++) {
		ll x = ll(b1.arr[i]) + b2.arr[i] + carry;
		b1.arr[i] = x;
		carry = (x >= (1ll << 32));
	}
}

static void operator -= (bigint2 &b1, bigint2 b2) {
	//b1 + (~b2) + 1
	//optimize the +1
	for (int i = 0; i < 18; i++) {
		b2.arr[i] = ~b2.arr[i];
	}
	b1 += b2;
	b1 += bigint2(1);
}

static bigint2 operator + (bigint2 b1, bigint2 b2) {
	b1 += b2;
	return b1;
}

static bigint2 operator - (bigint2 b1, bigint2 b2) {
	b1 -= b2;
	return b1;
}

static bool operator < (bigint2 b1, bigint2 b2) {
	for (int i = 17; i >= 0; i--) {
		if (b1.arr[i] < b2.arr[i]) {
			return true;
		}
		if (b1.arr[i] > b2.arr[i]) {
			return false;
		}
	}
	return false;
}

static bool operator >= (bigint2 b1, bigint2 b2) {
	return !(b1 < b2);
}

static bool operator > (bigint2 b1, bigint2 b2) {
	return b2 < b1;
}

static bool operator <= (bigint2 b1, bigint2 b2) {
	return !(b2 < b1);
}

static const int MAXV = 5 * 64 + 256;
static bigint2 cho[MAXV][256];
static void precomp() {
	for (int i = 0; i < MAXV; i++) {
		cho[i][0].arr[0] = 1;
		for (int j = 1; j <= i && j < 256; j++) {
			cho[i][j] = cho[i - 1][j] + cho[i - 1][j - 1];
		}
	}
}

static bigint2 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();
	sort(X, X + K);
	//find the rank of this one
	bigint2 rnk = bigint2();
	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
			bigint2 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.arr[i / 4] >> (8 * (i % 4))) & 255;
		//printf(" %d", val);
		output(val);
	}
	//printf("\n");
}

Compilation message

encoder.cpp:72:13: warning: 'bool operator<=(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bool operator <= (bigint1 b1, bigint1 b2) {
             ^~~~~~~~
encoder.cpp:68:13: warning: 'bool operator>(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bool operator > (bigint1 b1, bigint1 b2) {
             ^~~~~~~~
encoder.cpp:47:16: warning: 'bigint1 operator-(bigint1, bigint1)' defined but not used [-Wunused-function]
 static bigint1 operator - (bigint1 b1, bigint1 b2) {
                ^~~~~~~~

decoder.cpp:72:13: warning: 'bool operator<=(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator <= (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:68:13: warning: 'bool operator>(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator > (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:64:13: warning: 'bool operator>=(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bool operator >= (bigint2 b1, bigint2 b2) {
             ^~~~~~~~
decoder.cpp:47:16: warning: 'bigint2 operator-(bigint2, bigint2)' defined but not used [-Wunused-function]
 static bigint2 operator - (bigint2 b1, bigint2 b2) {
                ^~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 21636 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 22864 KB Output is correct
2 Correct 591 ms 22864 KB Output is correct
3 Correct 640 ms 22864 KB Output is correct
4 Correct 692 ms 22864 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 22864 KB Output is correct
2 Correct 651 ms 23048 KB Output is correct
3 Correct 663 ms 23080 KB Output is correct
4 Correct 742 ms 23080 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 23080 KB Output is correct
2 Correct 740 ms 23248 KB Output is correct
3 Correct 661 ms 23296 KB Output is correct
4 Correct 717 ms 23296 KB Output is correct
5 Correct 726 ms 23504 KB Output is correct
6 Correct 816 ms 23504 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 23504 KB Output is correct - P = 5.000000
2 Correct 641 ms 23504 KB Output is correct - P = 5.000000
3 Correct 663 ms 23504 KB Output is correct - P = 5.000000
4 Correct 603 ms 23712 KB Output is correct - P = 5.000000
5 Correct 675 ms 23712 KB Output is correct - P = 5.000000
6 Correct 615 ms 23712 KB Output is correct - P = 5.000000
7 Correct 610 ms 23712 KB Output is correct - P = 5.000000