Submission #926498

#	Time	Username	Problem	Language	Result	Execution time	Memory
926498		hotboy2703	Parrots (IOI11_parrots)	C++14	81 / 100	41 ms	3880 KiB

encoder

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
namespace {
    ll p[101][256];
    void init(){
        mt19937_64 rng(69420);
        for (ll i = 0;i < 100;i ++){
            for (ll j = 0;j < 256;j ++){
                p[i][j] = j;
            }
            shuffle(p[i],p[i]+256,rng);
        }
    }
}
void encode(int N, int M[]){
    init();
    ll n = N;
    vector <bool> all;
    for (ll i = 0;i < n;i ++){M[i] = p[i][M[i]];}
    for (ll i = 0;i < n;i ++)for (ll j = 0;j < 8;j ++)all.push_back(BIT(M[i],j));
    ll cnt[2];
    for (auto x:all)cnt[x]++;
    if (cnt[1] < 4 * n){
        all.insert(all.begin(),0);
        for (ll i = 1;i < sz(all);i++)all[i] = 1-all[i];
    }
    else{
        all.insert(all.begin(),1);
    }
//    for (auto x:all)cout<<x;
//    cout<<endl;
    cnt[0] = cnt[1] = 0;
    for (auto x:all){
        cnt[x]++;
        if (x==1){
            send(cnt[0]);
        }
    }
}

decoder

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
namespace {
    ll p[101][256];
    void init(){
        mt19937_64 rng(69420);
        for (ll i = 0;i < 100;i ++){
            for (ll j = 0;j < 256;j ++){
                p[i][j] = j;
            }
            shuffle(p[i],p[i]+256,rng);
        }
    }
}
void decode(int N, int L, int X[]){
    init();
    ll n = N;
    ll cnt[300] = {};
    for (ll i = 0;i < L;i ++){
        cnt[X[i]]++;
    }
    vector <ll> bit;
    for (ll i = 0;i < 256;i ++){
        while (cnt[i]--){
            bit.push_back(i);
        }
    }
    vector <bool> all;
    ll last = 0;
    for (auto x:bit){
        for (ll i= 0 ;i  < x - last;i ++){
            all.push_back(0);
        }
        all.push_back(1);
        last = x;
    }
    while (sz(all)<300)all.push_back(0);
//    for (auto x:all)cout<<x;
//    cout<<endl;
    if (all[0] == 0){
        for (ll j = 0;j < sz(all);j ++)all[j] = 1-all[j];
    }
    for (ll i = 0,ptr = 1;i < n;i ++,ptr += 8){
        ll res = 0;
        for (ll j = 0;j < 8;j ++){
            res += MASK(j) * all[ptr+j];
        }
//        cout<<i<<' '<<res<<endl;
        for (ll j = 0;j < 256;j ++){
            if (p[i][j]==res){
//                cout<<i<<' '<<j<<endl;
                output(j);
            }
        }
    }
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 0 / 19