oj.uz

답안 #106285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106285 2019-04-17T19:03:05 Z tincamatei 앵무새 (IOI11_parrots) C++14
100 / 100
 269 ms 168216 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_DIGITS = 64;
const int BASE = 256;

struct HugeNumber {
	int nr[MAX_DIGITS];

	HugeNumber() {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = 0;
	}
	HugeNumber(int x) {
		for(int i = 0; i < MAX_DIGITS; ++i) {
			nr[i] = x % BASE;
			x /= BASE;
		}
	}

	HugeNumber operator+(const HugeNumber &x) const {
		HugeNumber rez;
		int t = 0;

		for(int i = 0; i < MAX_DIGITS; ++i) {
			t = (t + x.nr[i] + nr[i]);
			rez.nr[i] = t % BASE;
			t /= BASE;
		}

		return rez;
	}

	HugeNumber operator++() {
		int i = 0;
		while(i < MAX_DIGITS && nr[i] == BASE - 1) {
			nr[i] = 0;
			++i;
		}
		if(i < MAX_DIGITS)
			nr[i]++;
		return *this;
	}

	void operator=(const HugeNumber &x) {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = x.nr[i];
	}

	HugeNumber operator~() const {
		HugeNumber rez;

		for(int i = 0; i < MAX_DIGITS; ++i)
			rez.nr[i] = BASE - nr[i] - 1;
		return rez;
	}

	HugeNumber operator-(const HugeNumber &x) const {
		HugeNumber y = ~x;
		++y;

		return *this + y;
	}

	bool operator>= (const HugeNumber &x) const {
		int i = MAX_DIGITS - 1;
		
		while(i > 0 && nr[i] == x.nr[i])
			--i;
		return nr[i] >= x.nr[i];
	}
};

void putHuge(HugeNumber x) {
	for(int i = 4; i >= 0; --i)
		printf("(%d)", x.nr[i]);
	printf(" ");
}

const int MAX_COMB = 575;

HugeNumber comb[1+MAX_COMB][1+MAX_COMB];
bool initted = false;

void initCommon() {
	if(!initted) {
		initted = true;
		for(int i = 0; i <= MAX_COMB; ++i)
			for(int j = 0; j <= i; ++j)
				if(i == j || j == 0)
					++comb[i][j];
				else
					comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
	}
}

vector<int> snb(HugeNumber x, int pigeons) {
	int numbers = 256;

	int n = pigeons + numbers - 1;
	int k = pigeons;

	vector<int> rez;
	while(n > 0) {
		if(x >= comb[n - 1][k]) {
			x = x - comb[n - 1][k];
			rez.push_back(numbers - 1);
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

void encode(int N, int M[]) {
	initCommon();
	
	HugeNumber data;
	for(int i = N - 1; i >= 0; --i)
  	data.nr[i] = M[i];
	
	vector<int> pigeons;
	pigeons = snb(data, 5 * N);

	for(auto it: pigeons)
		send(it);
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

namespace Decoder {

const int MAX_DIGITS = 64;
const int BASE = 256;

struct HugeNumber {
	int nr[MAX_DIGITS];

	HugeNumber() {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = 0;
	}
	HugeNumber(int x) {
		for(int i = 0; i < MAX_DIGITS; ++i) {
			nr[i] = x % BASE;
			x /= BASE;
		}
	}

	HugeNumber operator+(const HugeNumber &x) const {
		HugeNumber rez;
		int t = 0;

		for(int i = 0; i < MAX_DIGITS; ++i) {
			t = (t + x.nr[i] + nr[i]);
			rez.nr[i] = t % BASE;
			t /= BASE;
		}

		return rez;
	}

	HugeNumber operator++() {
		int i = 0;
		while(i < MAX_DIGITS && nr[i] == BASE - 1) {
			nr[i] = 0;
			++i;
		}
		if(i < MAX_DIGITS)
			nr[i]++;
		return *this;
	}

	void operator=(const HugeNumber &x) {
		for(int i = 0; i < MAX_DIGITS; ++i)
			nr[i] = x.nr[i];
	}

	HugeNumber operator~() const {
		HugeNumber rez;

		for(int i = 0; i < MAX_DIGITS; ++i)
			rez.nr[i] = BASE - nr[i] - 1;
		return rez;
	}

	HugeNumber operator-(const HugeNumber &x) const {
		HugeNumber y = ~x;
		++y;

		return *this + y;
	}

	bool operator>= (const HugeNumber &x) const {
		int i = MAX_DIGITS - 1;
		
		while(i > 0 && nr[i] == x.nr[i])
			--i;
		return nr[i] >= x.nr[i];
	}
};

void putHuge(HugeNumber x) {
	for(int i = 4; i >= 0; --i)
		printf("(%d)", x.nr[i]);
	printf(" ");
}

const int MAX_COMB = 575;

HugeNumber comb[1+MAX_COMB][1+MAX_COMB];
bool initted = false;

void initCommon() {
	if(!initted) {
		initted = true;
		for(int i = 0; i <= MAX_COMB; ++i)
			for(int j = 0; j <= i; ++j)
				if(i == j || j == 0)
					++comb[i][j];
				else
					comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
	}
}

vector<int> snb(HugeNumber x, int pigeons) {
	int numbers = 256;

	int n = pigeons + numbers - 1;
	int k = pigeons;

	vector<int> rez;
	while(n > 0) {
		if(x >= comb[n - 1][k]) {
			x = x - comb[n - 1][k];
			rez.push_back(numbers - 1);
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

HugeNumber invSnB(vector<int> v) {
	int n = v.size() + 256 - 1, k = v.size();
	int numbers = 255, pigeons = 0;

	HugeNumber rez;

	while(n > 0) {
		if(pigeons < v.size() && v[pigeons] == numbers) {
			pigeons++;
			rez = rez + comb[n - 1][k];
			n--;
			k--;
		} else {
			numbers--;
			n--;
		}
	}
	return rez;
}

}

void decode(int N, int L, int X[]) {
	using namespace Decoder;
	initCommon();
  
	vector<int> pigeons;
	for(int i = 0; i < L; ++i)
		pigeons.push_back(X[i]);
	
	sort(pigeons.rbegin(), pigeons.rend());
	HugeNumber rez = invSnB(pigeons);

	for(int i = 0; i < N; ++i)
		output(rez.nr[i]);
}

Compilation message

decoder.cpp: In function 'Decoder::HugeNumber Decoder::invSnB(std::vector<int>)':
decoder.cpp:130:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pigeons < v.size() && v[pigeons] == numbers) {
      ~~~~~~~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 167752 KB Output is correct
2 Correct 230 ms 167816 KB Output is correct
3 Correct 222 ms 167664 KB Output is correct
4 Correct 229 ms 167672 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 167704 KB Output is correct
2 Correct 261 ms 167760 KB Output is correct
3 Correct 239 ms 167664 KB Output is correct
4 Correct 239 ms 167664 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 167872 KB Output is correct
2 Correct 241 ms 167928 KB Output is correct
3 Correct 240 ms 167920 KB Output is correct
4 Correct 247 ms 167744 KB Output is correct
5 Correct 238 ms 167672 KB Output is correct
6 Correct 237 ms 167920 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 167824 KB Output is correct - P = 5.000000
2 Correct 241 ms 167920 KB Output is correct - P = 5.000000
3 Correct 244 ms 167824 KB Output is correct - P = 5.000000
4 Correct 247 ms 167920 KB Output is correct - P = 5.000000
5 Correct 244 ms 168216 KB Output is correct - P = 5.000000
6 Correct 241 ms 167920 KB Output is correct - P = 5.000000
7 Correct 269 ms 167920 KB Output is correct - P = 5.000000