oj.uz

Submission #961399

# Submission time Handle Problem Language Result Execution time Memory
961399 2024-04-12T03:44:44 Z emptypringlescan Parrots (IOI11_parrots) C++17
89.125 / 100
 19 ms 2092 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void encode(int n, int m[]){
	if(n>32) for(int i=0; i<6*n; i++) send(255);
	mt19937 rng(177013);
	int t=n*8,cnt=0;
	for(int i=0; i<n; i++){
		for(int j=7; j>=0; j--){
			if(m[i]>>j&1) cnt++;
		}
	}
	int num=0,x=0;
	if(cnt==t/2){
		while(true){
			num++;
			x=rng()%t;
			if(m[x/8]>>(x%8)&1){
				m[x/8]^=1<<(x%8);
				for(int i=0; i<num+1; i++) send(255);
				break;
			}
		}
	}
	int prev=0;
	if(cnt<=t/2){
		for(int i=0; i<n; i++){
			for(int j=0; j<8; j++){
				if(m[i]>>j&1){
					prev++;
					send(prev);
				}
				else send(prev);
			}
		}
	}
	else{
		for(int i=0; i<n; i++){
			for(int j=0; j<8; j++){
				if(!(m[i]>>j&1)){
					prev++;
					send(prev);
				}
				else send(prev);
			}
		}
		send(255);
	}
	if(num) m[x/8]^=1<<(x%8);
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void decode(int n, int l, int x[]){
	sort(x,x+l);
	assert(l>=8*n);
	mt19937 rng(177013);
	if(n>32) l-=6*n;
	int bits[8*n],ex=l-8*n;
	if(ex==1){
		int prev=0;
		for(int i=0; i<8*n; i++){
			bits[i]=x[i]-prev;
			prev=x[i];
			bits[i]^=1;
		}
	}
	else{
		int prev=0;
		for(int i=0; i<8*n; i++){
			bits[i]=x[i]-prev;
			prev=x[i];
		}
		if(ex>0){
			int y=0;
			for(int i=0; i<ex-1; i++) y=rng()%(8*n);
			//cout << y << ' ';
			bits[y]^=1;
		}
	}
	for(int i=0; i<n; i++){
		int ret=0;
		for(int j=0; j<8; j++){
			ret+=bits[i*8+j]<<j;
		}
		output(ret);
	}
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1320 KB Output is correct
2 Correct 2 ms 1316 KB Output is correct
3 Correct 3 ms 1320 KB Output is correct
4 Correct 3 ms 1320 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1312 KB Output is correct
2 Correct 2 ms 1520 KB Output is correct
3 Correct 3 ms 1356 KB Output is correct
4 Correct 3 ms 1316 KB Output is correct

Subtask #4
29.0 / 29.0

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

Subtask #5
8.125 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1328 KB Output is partially correct - P = 8.125000
2 Partially correct 4 ms 1348 KB Output is partially correct - P = 8.218750
3 Partially correct 8 ms 1388 KB Output is partially correct - P = 14.030303
4 Partially correct 15 ms 1704 KB Output is partially correct - P = 14.040000
5 Partially correct 19 ms 1996 KB Output is partially correct - P = 14.033333
6 Partially correct 19 ms 2092 KB Output is partially correct - P = 14.111111
7 Partially correct 18 ms 1988 KB Output is partially correct - P = 14.031250