oj.uz

Submission #285951

# Submission time Handle Problem Language Result Execution time Memory
285951 2020-08-29T19:16:50 Z Kastanda Parrots (IOI11_parrots) C++11
99 / 100
 14 ms 1792 KB 
// M
#include<bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;

const int N = 256, LIM = 7;
int ts1;
vector < int > TMp1, V1[N];
void Run1(int nw, int bt)
{
        if (ts1 >= N)
                return ;
        if (nw >= bt)
                return void(V1[ts1 ++] = TMp1);
        for (int i = 0; (int)TMp1.size() + i <= LIM; i ++)
        {
                for (int j = 0; j < i; j ++)
                        TMp1.push_back(nw);
                Run1(nw + 1, bt);
                for (int j = 0; j < i; j ++)
                        TMp1.pop_back();
        }
}
void Generate1(int lg)
{
        ts1 = 0;
        int bts = 8 - lg;
        int k = 1 << bts;

        Run1(0, k);
        assert(ts1 >= N);
}

void encode(int n, int B[])
{
        int lg = 6;
        if (n <= 32)
                lg = 5;

        vector < int > A(n);
        for (int i = 0; i < n; i ++)
                A[i] = B[i];

        Generate1(lg);

        for (int i = 1; i < n; i ++)
                A[i] = A[i] ^ A[i - 1];

        for (int i = 0; i < n; i ++)
                for (int a : V1[A[i]])
                        send((a << lg) | i);
}
// M
#include<bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;

const int N = 256, LIM = 7;
int ts2;
vector < int > TMp2;
map < vector < int > , int > MP;
void Run2(int nw, int bt)
{
        if (ts2 >= N)
                return ;
        if (nw >= bt)
                return void(MP[TMp2] = ts2 ++);
        for (int i = 0; (int)TMp2.size() + i <= LIM; i ++)
        {
                for (int j = 0; j < i; j ++)
                        TMp2.push_back(nw);
                Run2(nw + 1, bt);
                for (int j = 0; j < i; j ++)
                        TMp2.pop_back();
        }
}
void Generate2(int lg)
{
        ts2 = 0;
        int bts = 8 - lg;
        int k = 1 << bts;

        Run2(0, k);
        assert(ts2 >= N);
}
void decode(int n, int L, int X[])
{
        int lg = 6;
        if (n <= 32)
                lg = 5;

        Generate2(lg);

        vector < int > vec[64];
        for (int i = 0; i < L; i ++)
                vec[(X[i] & ((1 << lg) - 1))].push_back(X[i] >> lg);

        vector < int > A(n, 0);
        for (int i = 0; i < n; i ++)
        {
                sort(vec[i].begin(), vec[i].end());
                A[i] = MP[vec[i]];
        }

        for (int i = n - 1; i; i --)
                A[i] ^= A[i - 1];

        for (int i = 0; i < n; i ++)
                output(A[i]);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1600 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 6 ms 1536 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 8 ms 1792 KB Output is correct
6 Correct 8 ms 1792 KB Output is correct

Subtask #5
18.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 1536 KB Output is partially correct - P = 6.000000
2 Partially correct 8 ms 1792 KB Output is partially correct - P = 5.968750
3 Partially correct 8 ms 1792 KB Output is partially correct - P = 5.939394
4 Partially correct 11 ms 1792 KB Output is partially correct - P = 5.880000
5 Partially correct 12 ms 1792 KB Output is partially correct - P = 5.716667
6 Partially correct 13 ms 1792 KB Output is partially correct - P = 5.920635
7 Partially correct 14 ms 1792 KB Output is partially correct - P = 5.703125