oj.uz

답안 #262124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262124 2020-08-12T11:30:10 Z maximath_1 앵무새 (IOI11_parrots) C++11
100 / 100
 250 ms 152560 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;

struct big_num{
	short arr[105];
	void init(int x){
		memset(arr, 0, sizeof(arr));
		arr[0] = (short)x;
	}
};
big_num operator+(big_num a, big_num b){
	for(int i = 0; i < 100; i ++){
		int tp = (int)a.arr[i] + (int)b.arr[i];
		if(tp >= 256){
			tp -= 256;
			a.arr[i + 1] ++;
		}
		a.arr[i] = (short)tp;
	}
	return a;
}
bool operator<(big_num a, big_num b){
	for(int i = 104; i >= 0; i --){
		if(a.arr[i] < b.arr[i]) return 1;
		if(a.arr[i] > b.arr[i]) return 0;
	}
	return 0;
}

big_num C[605][605];
bool done = false;

void encode(int N, int M[]){
	if(!done){
		for(int i = 0; i < 605; i ++){
			C[i][0].init(1);
			for(int j = 1; j <= i; j ++){
				C[i][j].init(0);
				C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
			}
			for(int j = i + 1; j < 605; j ++)
				C[i][j].init(0);
		}
		done = 1;
	}

	big_num base, nw;
	nw.init(0); base.init(0);
	for(int i = 0; i < N; i ++) nw.arr[i] = M[i];
	nw = nw + base;
	base.init(0);
	int len = 255 + 5 * N;
	for(int i = 0; i < 5 * N; i ++){
		while(nw < C[len - 1][5 * N - i] + base) len --;
		send(5 * N + 255 - len - i - 1);
		base = base + C[len - 1][5 * N - i];
		len --;
	}
}
#include "decoder.h"
#include "decoderlib.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;

struct big__num{
	short arr[105];
	void init(int x){
		memset(arr, 0, sizeof(arr));
		arr[0] = (short)x;
	}
};
big__num operator+(big__num a, big__num b){
	for(int i = 0; i < 100; i ++){
		int tp = (int)a.arr[i] + (int)b.arr[i];
		if(tp >= 256){
			tp -= 256;
			a.arr[i + 1] ++;
		}
		a.arr[i] = (short)tp;
	}
	return a;
}
bool operator<(big__num a, big__num b){
	for(int i = 104; i >= 0; i --){
		if(a.arr[i] < b.arr[i]) return 1;
		if(a.arr[i] > b.arr[i]) return 0;
	}
	return 0;
}

big__num C_[605][605];
bool done_ = false;

void decode(int N, int L, int X[]){
	if(!done_){
		for(int i = 0; i < 605; i ++){
			C_[i][0].init(1);
			for(int j = 1; j <= i; j ++){
				C_[i][j].init(0);
				C_[i][j] = C_[i - 1][j] + C_[i - 1][j - 1];
			}
			for(int j = i + 1; j < 605; j ++)
				C_[i][j].init(0);
		}
		done_ = 1;
	}

	sort(X, X + L);

	big__num res; res.init(0);
	for(int i = 0; i < L; i ++)
		res = res + C_[5 * N + 255 - X[i] - i - 2][5 * N - i];
	for(int i = 0; i < N; i ++)
		output(res.arr[i]);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 151792 KB Output is correct
2 Correct 221 ms 152192 KB Output is correct
3 Correct 250 ms 152048 KB Output is correct
4 Correct 221 ms 152048 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 152304 KB Output is correct
2 Correct 231 ms 152048 KB Output is correct
3 Correct 226 ms 152048 KB Output is correct
4 Correct 221 ms 152048 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 152048 KB Output is correct
2 Correct 237 ms 152048 KB Output is correct
3 Correct 226 ms 152048 KB Output is correct
4 Correct 226 ms 151968 KB Output is correct
5 Correct 228 ms 152048 KB Output is correct
6 Correct 229 ms 152096 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 152048 KB Output is correct - P = 5.000000
2 Correct 235 ms 152312 KB Output is correct - P = 5.000000
3 Correct 227 ms 152048 KB Output is correct - P = 5.000000
4 Correct 238 ms 152560 KB Output is correct - P = 5.000000
5 Correct 247 ms 152048 KB Output is correct - P = 5.000000
6 Correct 247 ms 152048 KB Output is correct - P = 5.000000
7 Correct 246 ms 152048 KB Output is correct - P = 5.000000