oj.uz

답안 #961403

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961403 2024-04-12T03:49:10 Z emptypringlescan 앵무새 (IOI11_parrots) C++17
90.5152 / 100
 12 ms 1716 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
void encode(int n, int m[]){
	if(n>=16) for(int i=0; i<(int)(1.5*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>=16) l-=(int)(1.5*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

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1316 KB Output is correct
2 Correct 2 ms 1312 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1332 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 2 ms 1320 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 3 ms 1324 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1308 KB Output is correct
2 Correct 3 ms 1716 KB Output is correct
3 Correct 3 ms 1332 KB Output is correct
4 Correct 5 ms 1456 KB Output is correct
5 Correct 9 ms 1476 KB Output is correct
6 Correct 6 ms 1352 KB Output is correct

Subtask #5
9.515152 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 ms 1324 KB Output is partially correct - P = 9.625000
2 Partially correct 5 ms 1352 KB Output is partially correct - P = 9.718750
3 Partially correct 6 ms 1360 KB Output is partially correct - P = 9.515152
4 Partially correct 10 ms 1392 KB Output is partially correct - P = 9.540000
5 Partially correct 12 ms 1472 KB Output is partially correct - P = 9.533333
6 Partially correct 12 ms 1412 KB Output is partially correct - P = 9.603175
7 Partially correct 12 ms 1412 KB Output is partially correct - P = 9.531250