oj.uz

Submission #923367

# Submission time Handle Problem Language Result Execution time Memory
923367 2024-02-07T07:00:36 Z bachhoangxuan Parrots (IOI11_parrots) C++17
98 / 100
 7 ms 1560 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxa = 256;
#define pii pair<int,int>
#define fi first
#define se second

void encode(int N, int M[])
{
    pii Min={13*N,-1};
    for(int mask=0;mask<(1<<8);mask++){
        if(__builtin_popcount(mask)!=4) continue;
        int total=0;
        for(int i=0;i<N;i++){
            int d0=mask&M[i],d1=M[i]^d0;
            d0=__builtin_popcount(d0);
            d1=__builtin_popcount(d1);
            total+=d0+2*d1;
        }
        Min=min(Min,{total+4,mask<<1});
        Min=min(Min,{12*N-total+8,mask<<1|1});
    }
    int mask=Min.se>>1,rev=Min.se&1;
    for(int i=0;i<(1+rev)*4;i++) send(mask);
    vector<int> p0,p1;
    for(int i=0;i<8;i++){
        if(mask>>i&1) p0.push_back(i);
        else p1.push_back(i);
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<4;j++){
            int cnt=(M[i]>>p1[j]&1)<<1|(M[i]>>p0[j]&1);
            if(rev) cnt=3-cnt;
            for(int k=0;k<cnt;k++) send(i<<2|j);
        }
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxa = 256;

int cnt[maxa];

void decode(int N, int L, int X[])
{
    for(int i=0;i<maxa;i++) cnt[i]=0;
    for(int i=0;i<L;i++) cnt[X[i]]++;
    int rev=0,mask=-1;
    for(int i=0;i<maxa;i++){
        if(cnt[i]>=4){
            mask=i;
            cnt[i]-=4;
        }
        if(cnt[i]>=4){
            rev=1;
            cnt[i]-=4;
        }
    }
    if(rev){
        for(int i=0;i<maxa;i++) cnt[i]=3-cnt[i];
    }
    vector<int> p0,p1;
    for(int i=0;i<8;i++){
        if(mask>>i&1) p0.push_back(i);
        else p1.push_back(i);
    }
    for(int i=0;i<N;i++){
        int cur=0;
        for(int j=0;j<4;j++){
            cur+=(cnt[i<<2|j]&1)<<p0[j];
            cur+=(cnt[i<<2|j]>>1)<<p1[j];
        }
        output(cur);
    }
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1312 KB Output is correct
2 Correct 1 ms 1560 KB Output is correct
3 Correct 2 ms 1320 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 1 ms 1552 KB Output is correct
2 Correct 3 ms 1312 KB Output is correct
3 Correct 3 ms 1312 KB Output is correct
4 Correct 4 ms 1328 KB Output is correct
5 Correct 4 ms 1328 KB Output is correct
6 Correct 5 ms 1332 KB Output is correct

Subtask #5
17.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1312 KB partially correct P=6.125000
2 Partially correct 4 ms 1328 KB partially correct P=5.937500
3 Partially correct 4 ms 1328 KB partially correct P=6.000000
4 Partially correct 5 ms 1348 KB partially correct P=5.960000
5 Partially correct 6 ms 1312 KB partially correct P=5.966667
6 Partially correct 7 ms 1360 KB partially correct P=5.936508
7 Partially correct 6 ms 1380 KB partially correct P=5.968750