oj.uz

Submission #595217

# Submission time Handle Problem Language Result Execution time Memory
595217 2022-07-13T12:45:11 Z Bench0310 Parrots (IOI11_parrots) C++17
100 / 100
 7 ms 1348 KB 
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"

using namespace std;
typedef long long ll;

static const int S=20;
static ll C[2*S+1][2*S+1];

static void ini()
{
    for(int i=0;i<=2*S;i++) C[i][0]=1;
    for(int i=1;i<=2*S;i++) for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}

static ll opt(int n,int m){return C[n+m-1][n];}

array<int,16> enc(array<int,4> a,int cnt)
{
    reverse(a.begin(),a.end());
    ll b=0;
    for(int i=0;i<4;i++) b=(b<<8)+a[i];
    array<int,16> c;
    c.fill(0);
    for(int i=0;i<16;i++)
    {
        while(cnt>0&&opt(cnt,16-i)<=b)
        {
            b-=opt(cnt,16-i);
            c[i]++;
            cnt--;
        }
    }
    assert(b==0);
    return c;
}

void encode(int N,int M[])
{
    ini();
    for(int i=0;i<N;i+=4)
    {
        array<int,4> a;
        a.fill(0);
        for(int j=0;j<4&&i+j<N;j++) a[j]=M[i+j];
        array<int,16> c=enc(a,5*min(4,N-i));
        for(int j=0;j<16;j++) for(int k=0;k<c[j];k++) send(((i>>2)<<4)+j);
    }
}

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"

using namespace std;
typedef long long ll;

static const int S=20;
static ll C[2*S+1][2*S+1];

static void ini()
{
    for(int i=0;i<=2*S;i++) C[i][0]=1;
    for(int i=1;i<=2*S;i++) for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}

static ll opt(int n,int m){return C[n+m-1][n];}

array<int,4> dec(array<int,16> c,int cnt)
{
    ll b=0;
    for(int i=0;i<16;i++)
    {
        while(c[i]--)
        {
            b+=opt(cnt,16-i);
            cnt--;
        }
    }
    array<int,4> a;
    for(int i=3;i>=0;i--)
    {
        a[i]=(b&255);
        b>>=8;
    }
    reverse(a.begin(),a.end());
    return a;
}

void decode(int N,int L,int X[])
{
    ini();
    vector<array<int,16>> v(N);
    for(int i=0;i<N;i++) v[i].fill(0);
    for(int i=0;i<L;i++)
    {
        int x=X[i];
        v[(x>>4)<<2][x&15]++;
    }
    for(int i=0;i<N;i+=4)
    {
        array<int,4> a=dec(v[i],5*min(4,N-i));
        for(int j=0;j<4&&i+j<N;j++) output(a[j]);
    }
}

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 1040 KB Output is correct
2 Correct 2 ms 1012 KB Output is correct
3 Correct 2 ms 1040 KB Output is correct
4 Correct 2 ms 1040 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1040 KB Output is correct
2 Correct 2 ms 1036 KB Output is correct
3 Correct 2 ms 1012 KB Output is correct
4 Correct 2 ms 1052 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1032 KB Output is correct
2 Correct 3 ms 1044 KB Output is correct
3 Correct 3 ms 1056 KB Output is correct
4 Correct 3 ms 1184 KB Output is correct
5 Correct 3 ms 1192 KB Output is correct
6 Correct 5 ms 1184 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1040 KB Output is correct - P = 5.000000
2 Correct 3 ms 1192 KB Output is correct - P = 4.937500
3 Correct 4 ms 1188 KB Output is correct - P = 4.969697
4 Correct 6 ms 1312 KB Output is correct - P = 4.860000
5 Correct 7 ms 1348 KB Output is correct - P = 4.850000
6 Correct 6 ms 1348 KB Output is correct - P = 4.888889
7 Correct 6 ms 1328 KB Output is correct - P = 4.875000