oj.uz

Submission #926504

# Submission time Handle Problem Language Result Execution time Memory
926504 2024-02-13T07:23:49 Z hotboy2703 Parrots (IOI11_parrots) C++14
99 / 100
 25 ms 3688 KB 
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

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

const int maxn = 64;
const int maxv = 256;

int h[maxn][maxv];
int f[maxv], ans[maxn];
int ptr = 0;

void init(){
    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    ptr = 0;
    mt19937 rng(69);
    for(int i = 0; i < 64; i++){
        for(int j = 0; j < 256; j++){
            h[i][j] = j;
        }
        shuffle(h[i], h[i] + maxv, rng);
    }
}

void send_bit(int x){
//    cout<<"SEND BIT "<<x<<' '<<ptr<<endl;
    if(x && ptr < maxv)send(ptr);
    else ptr++;
}

void encode(int N, int M[])
{
    init();
    int cnt1 = 0;
    for(int i = 0; i < N; i++)cnt1 += __builtin_popcount(h[i][M[i]]);
    int sw = 0;
    if(cnt1 < N*4){
        sw = 1;
        send_bit(0);
    }
    else send_bit(1);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 8; j++){
            send_bit((h[i][M[i]]>>j&1)^sw);
        }
    }
}


#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

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

const int maxn = 64;
const int maxv = 256;

int h[maxn][maxv];
int f[maxv], ans[maxn];
int ptr = 0;

void init(){
    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    ptr = 0;
    mt19937 rng(69);
    for(int i = 0; i < 64; i++){
        for(int j = 0; j < 256; j++){
            h[i][j] = j;
        }
        shuffle(h[i], h[i] + maxv, rng);
    }
}

int get_bit(){
    if(ptr == maxv)return 1;
    else if(!f[ptr]){
        ptr++;
        return 0;
    }
    else {
        f[ptr]--;
        return 1;
    }
}


void decode(int N, int L, int X[])
{
    init();
    int sw = 0;
    for(int i = 0; i < L; i++)f[X[i]]++;
    if(!get_bit())sw = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 8; j++){
            ans[i] ^= (get_bit()^sw)<<j;
        }
        for(int j = 0; j < maxv; j++){
            if(h[i][j] == ans[i]){
                output(j);
                break;
            }
        }
    }
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2832 KB Output is correct
2 Correct 20 ms 2844 KB Output is correct
3 Correct 20 ms 2844 KB Output is correct
4 Correct 23 ms 2988 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2976 KB Output is correct
2 Correct 20 ms 2836 KB Output is correct
3 Correct 20 ms 2988 KB Output is correct
4 Correct 20 ms 2848 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2840 KB Output is correct
2 Correct 20 ms 2844 KB Output is correct
3 Correct 20 ms 2848 KB Output is correct
4 Correct 22 ms 2872 KB Output is correct
5 Correct 22 ms 2864 KB Output is correct
6 Correct 23 ms 3120 KB Output is correct

Subtask #5
18.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 3688 KB partially correct P=5.187500
2 Correct 23 ms 2856 KB Output is correct
3 Correct 24 ms 2996 KB Output is correct
4 Correct 25 ms 2872 KB Output is correct
5 Correct 24 ms 3076 KB Output is correct
6 Correct 24 ms 2900 KB Output is correct
7 Correct 25 ms 3076 KB Output is correct