oj.uz

Submission #770421

# Submission time Handle Problem Language Result Execution time Memory
770421 2023-07-01T07:43:09 Z adrilen Parrots (IOI11_parrots) C++17
81 / 100
 6 ms 1300 KB 
#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";
//         }
//     }
    

// }

#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.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 952 KB Output is correct
2 Correct 3 ms 1048 KB Output is correct
3 Correct 3 ms 1044 KB Output is correct
4 Correct 2 ms 1060 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 3 ms 1008 KB Output is correct
3 Correct 2 ms 1044 KB Output is correct
4 Correct 2 ms 1020 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1036 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 5 ms 1052 KB Output is correct
4 Correct 6 ms 1300 KB Output is correct
5 Correct 6 ms 1200 KB Output is correct
6 Correct 5 ms 1204 KB Output is correct

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 1048 KB Output is partially correct - P = 7.000000
2 Partially correct 5 ms 1204 KB Output is partially correct - P = 7.000000
3 Incorrect 1 ms 752 KB Error : Output length must be N
4 Incorrect 1 ms 772 KB Error : Output length must be N
5 Incorrect 1 ms 788 KB Error : Output length must be N
6 Incorrect 1 ms 800 KB Error : Output length must be N
7 Incorrect 1 ms 788 KB Error : Output length must be N