Submission #770421

#	Time	Username	Problem	Language	Result	Execution time	Memory
770421		adrilen	Parrots (IOI11_parrots)	C++17	81 / 100	6 ms	1300 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

/*
Can maybe send one bit from each number
The zeroth bit sent once
The first bit sent twice
THe third bit sent three times
.
.
.




Sending 8 bit numbers  
3 for the exact bit placement
3 for telling which group
2 for telling the actual bits

*/


/*
For 32/64
Have the first 5 bits tell the position, and then send three bits
Send one message for the first three bits, two identical messages for the next three bits


Need to have different cases for n = 64, and n = 32

We need to specify the position by sending it a power of two number of times, then we can distingluish 
copies

1+2+4+8 = 15, which is correct for n = 64, 

but for n = 32
we need 1 + 2 +4, which means that only the first 5 bits can be used for position
*/

void encode(int n, int M[])
{
    if (n <= 32)
    {
        int out;
        for (int i = 0; i < n; i++)
        {
            for (int y = 0; y < 8; y += 3)
            {
                out = (i << 3);

                out |= __builtin_popcount(M[i] & (1 << y));
                out |= __builtin_popcount(M[i] & (1 << (y + 1))) << 1;
                
                if (y != 6) out |= __builtin_popcount(M[i] & (1 << (y + 2))) << 2;

                for (int x = 0; x < (1 << (y / 3) ); x++) {
                    send(out);
                    // cout << bitset<8>(out) << "\n";
                }
            }
        }



    }
}




// void encode(int n, int M[])
// {
//     int groups = (n + 1) / 2;


//     for (int g = 0; g < groups; g++)
//     {
//         int out = (g << 5);
//         cout << out << "\n";
//         for (int b = 0; b < 8; b++)
//         {
//             out |= (b << 2);
//             cout << " " << out << "\n";


//             out |= ((M[g * 2] & (1 << b)) >> (b - 1));
//             cout << "  " << out << "\n";
//             out |= ((M[g * 2 + 1] & (1 << b)) >> b);
//             cout << "   " << out << "\n";
//         }
//     }
    

// }

decoder

#include "decoder.h"
#include "decoderlib.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
using pii = pair<int, int>;

void decode(int n, int l, int x[])
{
    map<int, int> m;
    for (int i = 0; i < l; i++)
    {
        if (m.count(x[i])) m[x[i]]++;
        else m[x[i]] = 1;
    }

    
    auto it = m.begin();

    int c = 0;
    int ou = 0;
    pii p;

    

    while (it != m.end())
    {
        p = *it++;

        p.first &= 7;

        if (p.second & 1) {
            ou |= p.first;
            c++;
        } 
        if (p.second & 2)
        {
            ou |= (p.first << 3);
            c++;
        } 
        if (p.second & 4) {
            ou |= (p.first << 6);
            c++;
        }

       

        if (c == 3) {
            // cout << "output: " << ou << "\n";
            output(ou);
            ou = 0;
            c = 0;
        }
    }
    




}

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