oj.uz

Submission #352037

# Submission time Handle Problem Language Result Execution time Memory
352037 2021-01-20T11:37:12 Z tengiz05 Parrots (IOI11_parrots) C++17
99 / 100
 8 ms 1572 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void print(int x){
	for(int i=128;i>=0;i>>=1){
		cout << ((x>>i)&1);
	}cout << '\n';
}
int A[100];
void encode(int n, int aa[]){
	for(int i=0;i<n;i++)A[i] = aa[i];
	int best_xor = 0;
	for(int j=0;j<8;j++){
		int cnt = 0;
		for(int i=0;i<n;i++){
			cnt += (A[i]>>j&1);
		}if(cnt > n/2)best_xor |= (1<<j);
	}
	send(best_xor);
	send(best_xor);
	send(best_xor);
	send(best_xor);
	for(int i=0;i<n;i++)A[i] ^= best_xor;
	for(int i=0;i<n;i++){
		while(A[i] >= 64){
			A[i] -= 64;
			send(i | (3<<6));
		}
		while(A[i] >= 16){
			A[i] -= 16;
			send(i | (2<<6));
		}
		while(A[i] >= 4){
			A[i] -= 4;
			send(i | (1<<6));
		}
		while(A[i] >= 1){
			A[i] -= 1;
			send(i | (0<<6));
		}
	}
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
int a[256], cnt[256];
void decode(int n, int len, int x[]){
	for(int i=0;i<256;i++)a[i]=0,cnt[i]=0;
	for(int i=0;i<len;i++)cnt[x[i]]++;
	int best_xor=0;
	for(int i=0;i<256;i++){
		if(cnt[i] > 3){
			cnt[i] -= 4;
			best_xor = i;
			break;
		}
	}
	for(int i=0;i<len;i++){
		if(!cnt[x[i]])continue;
		int type = (x[i] & 192)>>6;
		int ind = x[i] & 63;
		if(type == 3)a[ind] += 64,cnt[x[i]]--;
		if(!cnt[x[i]])continue;
		if(type == 2)a[ind] += 16,cnt[x[i]]--;
		if(!cnt[x[i]])continue;
		if(type == 1)a[ind] += 4,cnt[x[i]]--;
		if(!cnt[x[i]])continue;
		if(type == 0)a[ind] += 1,cnt[x[i]]--;
		if(!cnt[x[i]])continue;
	}
	//~ for(int i=0;i<n;i++)cout << a[i] << ' ';cout << '\n';	
	for(int i=0;i<n;i++)output(a[i]^best_xor);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1328 KB Output is correct
2 Correct 3 ms 1264 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1140 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1336 KB Output is correct
2 Correct 2 ms 1328 KB Output is correct
3 Correct 3 ms 1332 KB Output is correct
4 Correct 3 ms 1140 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 3 ms 1328 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 5 ms 1284 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 4 ms 1156 KB Output is correct

Subtask #5
18.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1320 KB Output is partially correct - P = 5.750000
2 Partially correct 5 ms 1156 KB Output is partially correct - P = 5.718750
3 Partially correct 4 ms 1284 KB Output is partially correct - P = 5.696970
4 Partially correct 7 ms 1304 KB Output is partially correct - P = 5.920000
5 Partially correct 8 ms 1444 KB Output is partially correct - P = 5.750000
6 Partially correct 8 ms 1572 KB Output is partially correct - P = 5.841270
7 Partially correct 8 ms 1532 KB Output is partially correct - P = 5.906250