oj.uz

Submission #41677

# Submission time Handle Problem Language Result Execution time Memory
41677 2018-02-20T12:09:36 Z tjd229 Parrots (IOI11_parrots) C++11
100 / 100
 131 ms 89904 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <memory.h>
//const int bnde = 264 + 256;
const int bnde = 64*5 + 256;
int ce[bnde][bnde][64];
void add(int dst[], int src1[], int src2[]){
	int nxt = 0;
	for (int i = 63; i >=0; i--){
		dst[i] = src1[i] + src2[i]+nxt;		
		nxt = dst[i] / 256;
		if (i)
			dst[i] %= 256;
		
	}
}
void subtract(int dst[],int src1[], int src2[]){
	for (int i = 0; i < 64; i++){
		dst[i] = src1[i] - src2[i];
	}
	for (int i = 63; i>0 ; i--){
		while (dst[i] < 0){
			dst[i] += 256;
			dst[i - 1]--;
		}
	}
}
int cmp(int a1[], int a2[]){
	for (int i = 0; i<64; i++){
		if (a1[i] > a2[i]) return -1;
		if (a1[i] < a2[i]) return 1;
	}
	return 0;
}
void set(){
	int i, j;
	for (i = 1; i < bnde; i++){
		ce[i][0][63] = ce[i][i][63] = 1;
	}
	for (i = 2; i < bnde; i++){
		for (j = 1; j < i; j++){	
			add(ce[i][j], ce[i - 1][j - 1], ce[i - 1][j]);
		}
	}
}
void encode(int N, int M[])
{
	static int flage = 0;
	int i,j;
	if (flage++ == 0) set();
	
	int msg[64] = { 0 };
	for (j = 64 - N, i = 0; i < N; i++,j++) msg[j] = M[i];
	//for (i = 0; i < N; i++) msg[i] = M[i];
	
	int parrot=262;
	for (i = 1; i < 320; i++){
		if (cmp(ce[i+256-1][i], msg) == -1){
			
			parrot = i;
			break;
		}
	}
	

	//int out[64] = { 0 };
	//int cnt[256] = { 0 };
	for (i = 0; i < 256&&parrot; i++){
		int a[64] = { 0 };
		int last[64] = { 0 };
		for (j = 0; j < 261&&parrot; j++){
			add(a, last, ce[parrot + 256 - i - 1 - 1][parrot]);
			
			if (cmp(a,msg) == -1) break;
			memcpy(last, a, sizeof(last));
			send(i);
			//cnt[i]++;
			parrot--;
		}
		memcpy(a, msg, sizeof(a));
		subtract(msg, a, last);
	}

}

#include "decoder.h"
#include "decoderlib.h"
const int bndd = 64*5 + 256;
int cd[bndd][bndd][64];
void addd(int dst[], int src1[], int src2[]){
	int nxt = 0;
	for (int i = 63; i >= 0; i--){
		dst[i] = src1[i] + src2[i] + nxt;
		nxt = dst[i] / 256;
		if (i)
			dst[i] %= 256;

	}
}
void set_cd(){
	int i, j;
	for (i = 1; i < bndd; i++){
		cd[i][0][63] = cd[i][i][63] = 1;
	}
	for (i = 2; i < bndd; i++){
		for (j = 1; j < i; j++){
			//printf("%d,%d\n",i,j);
			addd(cd[i][j], cd[i - 1][j - 1], cd[i - 1][j]);
		}
	}
}
void decode(int N, int L, int X[])
{
	static int flagd = 0;
	if (flagd++ == 0) set_cd();
	int i,j;
	int cnt[256] = { 0 };
	int recon[64] = { 0 };
	for (i = 0; i < L; i++)
		cnt[X[i]]++;
	int parrot = L;
	for (i = 0; i < 256; i++){
		for (j = 0; j < cnt[i]; j++){
			
			addd(recon, recon, cd[parrot + 256 - i - 1 - 1][parrot]);
			parrot--;
		}
	}
	for (i = 64-N; i < 64; i++){
		output(recon[i]);
	}
	
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 88304 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 89384 KB Output is correct
2 Correct 114 ms 89416 KB Output is correct
3 Correct 113 ms 89904 KB Output is correct
4 Correct 110 ms 89904 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 89904 KB Output is correct
2 Correct 109 ms 89904 KB Output is correct
3 Correct 111 ms 89904 KB Output is correct
4 Correct 114 ms 89904 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 89904 KB Output is correct
2 Correct 111 ms 89904 KB Output is correct
3 Correct 112 ms 89904 KB Output is correct
4 Correct 113 ms 89904 KB Output is correct
5 Correct 114 ms 89904 KB Output is correct
6 Correct 114 ms 89904 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 89904 KB Output is correct - P = 1.750000
2 Correct 117 ms 89904 KB Output is correct - P = 2.437500
3 Correct 113 ms 89904 KB Output is correct - P = 2.484848
4 Correct 119 ms 89904 KB Output is correct - P = 3.300000
5 Correct 127 ms 89904 KB Output is correct - P = 3.850000
6 Correct 128 ms 89904 KB Output is correct - P = 4.031746
7 Correct 131 ms 89904 KB Output is correct - P = 4.093750