oj.uz

Submission #584377

# Submission time Handle Problem Language Result Execution time Memory
584377 2022-06-27T09:34:48 Z benson1029 Parrots (IOI11_parrots) C++14
100 / 100
 7 ms 1360 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;

namespace encoder_var {
	long long ncr[50][50];

	void init() {
		for(int i=0; i<50; i++) {
			ncr[i][0] = ncr[i][i] = 1;
			for(int j=1; j<i; j++) {
				ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
			}
		}
	}

	long long nhr(int n, int r) {
		return ncr[n+r-1][r];
	}
};

void encode(int N, int M[])
{
	using namespace encoder_var;
	init();
	for(int i=0; i<N; i+=4) {
		int init = i*4;
		long long v = 0;
		for(int j=i+3; j>=i; j--) {
			v *= 256;
			if(j < N) v += M[j];
		}
		int prevv = 0;
		for(int j=0; j<20; j++) {
			int ans = 0;
			for(int k=prevv; k<=16; k++) {
				if(v < nhr(16-k+1, 20-j-1)) {
					ans = k;
					break;
				}
				v -= nhr(16-k+1, 20-j-1);
			}
			if(ans > 0) {
				send(init+ans-1);
			}
			prevv = ans;
		}
	}
}

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;

namespace decoder_var {
	long long ncr[50][50];
	vector<int> tmp;
	int a[1000];

	void init() {
		for(int i=0; i<50; i++) {
			ncr[i][0] = ncr[i][i] = 1;
			for(int j=1; j<i; j++) {
				ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
			}
		}
	}

	long long nhr(int n, int r) {
		return ncr[n+r-1][r];
	}
};

void decode(int N, int L, int X[])
{
	using namespace decoder_var;
	sort(X, X+L);
	init();
	int ptr = 0;
	for(int i=0; i<64; i+=4) {
		int init = i*4;
		tmp.clear();
		while(ptr<L && X[ptr]<init+16) {
			tmp.push_back(X[ptr]-init+1);
			++ptr;
		}
		while(tmp.size() < 20) tmp.push_back(0);
		sort(tmp.begin(), tmp.end());
		int prevv = 0;
		long long ans = 0;
		for(int j=0; j<tmp.size(); j++) {
			for(int k=prevv; k<tmp[j]; k++) {
				ans += nhr(16-k+1, 20-j-1);
			}
			prevv = tmp[j];
		}
		for(int j=i; j<i+4; j++) {
			a[j] = ans % 256;
			ans /= 256;
		}
	}
	for(int i=0; i<N; i++) output(a[i]);
}

Compilation message

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j=0; j<tmp.size(); j++) {
      |                ~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1008 KB Output is correct
2 Correct 2 ms 1048 KB Output is correct
3 Correct 2 ms 1008 KB Output is correct
4 Correct 3 ms 1020 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1040 KB Output is correct
2 Correct 2 ms 1048 KB Output is correct
3 Correct 2 ms 1036 KB Output is correct
4 Correct 3 ms 1176 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1008 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1048 KB Output is correct
4 Correct 4 ms 1184 KB Output is correct
5 Correct 3 ms 1192 KB Output is correct
6 Correct 3 ms 1192 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1008 KB Output is correct - P = 5.000000
2 Correct 4 ms 1192 KB Output is correct - P = 5.000000
3 Correct 4 ms 1192 KB Output is correct - P = 4.939394
4 Correct 6 ms 1324 KB Output is correct - P = 4.920000
5 Correct 7 ms 1344 KB Output is correct - P = 5.000000
6 Correct 6 ms 1360 KB Output is correct - P = 4.952381
7 Correct 7 ms 1348 KB Output is correct - P = 5.000000