Submission #767064

#	Time	Username	Problem	Language	Result	Execution time	Memory
767064		raysh07	Parrots (IOI11_parrots)	C++17	97 / 100	7 ms	1344 KiB

encoder

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

void encode(int n, int a[])
{
//   int i;
//   for(i=0; i<N; i++)
//     send(M[i]);
    if (n < 16){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 8; j++){
                if (a[i] >> j & 1){
                    send(8 * i + j);
                }
            }
        }
        return;
    }
    
    vector <int> b;
    vector <pair<int, int>> f(4);
    for (int i = 0; i < 4; i++){
        f[i] = {0, i};
    }
    for (int i = 0; i < n; i++){
        int copy = a[i];
        for (int j = 0; j < 4; j++){
            b.push_back(copy % 4);
            copy /= 4;
            f[b.back()].first++;
        }
    }
    
    sort(f.begin(), f.end());
    map <int, int> mp;
    for (int i = 0; i < 4; i++){
        mp[f[i].second] = 3 - i;
        //send f[i].second 3 - i times
        for (int j = 0; j < 4 * (3 - i); j++) send(f[i].second);
    }
    
    int val = 0;
    
    for (auto x : b){
        int y = mp[x];
        for (int i = 0; i < y; i++) send(val);
        val++;
    }
}

decoder

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

void decode(int n, int l, int a[])
{
    //l is length of encoded sequence
    //n is the answer we need 
    vector <int> cnt(256, 0);
    for (int i = 0; i < l; i++) cnt[a[i]]++;
    
    if (n < 16){
        vector <int> ans(n, 0);
        for (int i = 0; i < 256; i++){
            if (cnt[i] == 1){
                ans[i / 8] += 1 << (i % 8);
            }
        }
        
        for (int i = 0; i < n; i++){
            output(ans[i]);
        }
        return;
    }
    
    vector <int> ans(256, 0);
    vector <int> f(4, 0);
    f[0] = cnt[0] / 4;
    f[1] = cnt[1] / 4;
    f[2] = cnt[2] / 4;
    f[3] = cnt[3] / 4;
    
    for (int i = 0; i < 4; i++) cnt[i] %= 4;
    
    int mul = 1;
    
    for (int i = 0; i < 256; i++){
        if (i % 4 == 0) mul = 1;
        else mul *= 4;
        for (int j = 0; j < 4; j++){
            if (cnt[i] == f[j]){
                // int x = i % 4;
                // ans[i / 4] += (j % 2) * (1 << (2 * x));
                // ans[i / 4] += (j / 2) * (1 << (2 * x + 1));
                ans[i / 4] += j * mul;
            }
        }
    }
    for (int i = 0; i < n; i++) output(ans[i]);
}

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