oj.uz

Submission #923525

# Submission time Handle Problem Language Result Execution time Memory
923525 2024-02-07T11:34:09 Z bachhoangxuan Parrots (IOI11_parrots) C++17
100 / 100
 6 ms 1376 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const int maxa = 256;
const int Max = 35;
const int Lim = 27;
ll dp[55][55];


void encode(int N, int M[])
{
    for(int i=0;i<=Max;i++){
        for(int j=0;j<Lim;j++){
            dp[i][j]=!(i|j);
            if(i) dp[i][j]+=dp[i-1][j];
            if(j) dp[i][j]+=dp[i][j-1];
        }
    }
    int cur=0;
    for(int i=0;i<N;i+=7){
        ll num=0,mul=1;
        int cnt=0;
        for(int j=i;j<min(i+7,N);j++){
            num+=1LL*M[j]*mul,mul*=maxa,cnt++;
        }
        for(int j=cnt*5;j>=1;j--){
            for(int k=0;k<min(maxa-cur,Lim);k++){
                if(dp[j][k]>num){
                    if(k) num-=dp[j][k-1];
                    send(cur+k);
                    break;
                }
            }
        }
        cur+=Lim;
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxa = 256;
const int Max = 35;
const int Lim = 27;
ll dp[55][55];

void decode(int N, int L, int X[])
{
    for(int i=0;i<=Max;i++){
        for(int j=0;j<Lim;j++){
            dp[i][j]=!(i|j);
            if(i) dp[i][j]+=dp[i-1][j];
            if(j) dp[i][j]+=dp[i][j-1];
        }
    }
    vector<vector<int>> d(N);
    for(int i=0;i<L;i++) d[X[i]/Lim].push_back(X[i]%Lim);
    for(int i=0;i<N;i++){
        if(d[i].empty()) continue;
        sort(d[i].begin(),d[i].end());
        ll num=0;
        for(int j=(int)d[i].size();j>=1;j--){
            int k=d[i][j-1];
            if(k) num+=dp[j][k-1];
        }
        for(int j=i*7;j<min((i+1)*7,N);j++){
            output(num%maxa);
            num/=maxa;
        }
    }
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1312 KB Output is correct
2 Correct 2 ms 1316 KB Output is correct
3 Correct 2 ms 1320 KB Output is correct
4 Correct 2 ms 1312 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1300 KB Output is correct
2 Correct 3 ms 1308 KB Output is correct
3 Correct 3 ms 1308 KB Output is correct
4 Correct 3 ms 1312 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1304 KB Output is correct
2 Correct 2 ms 1320 KB Output is correct
3 Correct 3 ms 1312 KB Output is correct
4 Correct 3 ms 1324 KB Output is correct
5 Correct 3 ms 1336 KB Output is correct
6 Correct 3 ms 1336 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1320 KB Output is correct
2 Correct 3 ms 1324 KB Output is correct
3 Correct 3 ms 1336 KB Output is correct
4 Correct 5 ms 1356 KB Output is correct
5 Correct 6 ms 1360 KB Output is correct
6 Correct 6 ms 1376 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct