oj.uz

Submission #895629

# Submission time Handle Problem Language Result Execution time Memory
895629 2023-12-30T12:10:51 Z abcvuitunggio Parrots (IOI11_parrots) C++17
100 / 100
 103 ms 36736 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=1000000000;
static struct bignum{
    vector <int> d;
}dp[301][301];
static bignum f(int x){
    if (!x)
        return {{0}};
    bignum a;
    for (;x;x/=base)
        a.d.push_back(x%base);
    return a;
}
static bool operator <(bignum a, bignum b){
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    while (b.d.size()<a.d.size())
        b.d.push_back(0);
    for (int i=a.d.size()-1;i>=0;i--)
        if (a.d[i]!=b.d[i])
            return a.d[i]<b.d[i];
    return false;
}
static bignum operator +(bignum a, bignum b){
    bignum c;
    if (a.d.size()>b.d.size())
        swap(a,b);
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]+b.d[i]+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    if (carry)
        c.d.push_back(carry);
    return c;
}
static bignum operator -(bignum a, bignum b){
    bignum c;
    while (a.d.size()>b.d.size())
        b.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]-b.d[i]-carry;
        if (x<0){
            x+=base;
            carry=1;
        }
        else
            carry=0;
        c.d.push_back(x);
    }
    return c;
}
static bignum operator *(bignum a, int b){
    bignum c;
    long long carry=0;
    for (int i=0;i<a.d.size();i++){
        long long x=1LL*a.d[i]*b+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    for (;carry;carry/=base)
        c.d.push_back(carry%base);
    return c;
}
static bignum calc(int i, int j){
    if (i<0)
        return {{0}};
    if (j<0)
        return {{1}};
    if (!dp[i][j].d.empty())
        return dp[i][j];
    return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void encode(int N, int M[]){
    bignum val={{0}};
    for (int i=N-1;i>=0;i--)
        val=val*256+f(M[i]);
    int n=0,i=0;
    while (calc(255,n)<val)
        n++;
    for (int j=0;j<=n;j++){
        while (calc(255-i,n-j-1)-f(1)<val){
            val=val-calc(255-i,n-j-1);
            i++;
        }
        send(i);
    }
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
static const int base=10;
static struct bignum{
    vector <int> d;
}dp[301][301];
static bignum f(int x){
    if (!x)
        return {{0}};
    bignum a;
    for (;x;x/=base)
        a.d.push_back(x%base);
    return a;
}
static bignum operator +(bignum a, bignum b){
    bignum c;
    if (a.d.size()>b.d.size())
        swap(a,b);
    while (a.d.size()<b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]+b.d[i]+carry;
        c.d.push_back(x%base);
        carry=x/base;
    }
    if (carry)
        c.d.push_back(carry);
    return c;
}
static bignum operator -(bignum a, bignum b){
    bignum c;
    while (a.d.size()>b.d.size())
        a.d.push_back(0);
    int carry=0;
    for (int i=0;i<a.d.size();i++){
        int x=a.d[i]-b.d[i]-carry;
        if (x<0){
            x+=base;
            carry=1;
        }
        c.d.push_back(x);
    }
    return c;
}
static pair <bignum, int> operator /(bignum a, int b){
    bignum c;
    int carry=0;
    for (int i=a.d.size()-1;i>=0;i--){
        long long x=carry*base+a.d[i];
        if (x/b||!c.d.empty())
            c.d.push_back(x/b);
        carry=x%b;
    }
    reverse(c.d.begin(),c.d.end());
    return {c,carry};
}
static bignum calc(int i, int j){
    if (i<0||j<0)
        return {{0}};
    if (!i&&!j)
        return {{1}};
    if (!dp[i][j].d.empty())
        return dp[i][j];
    return dp[i][j]=calc(i-1,j)+calc(i,j-1);
}
void decode(int N, int L, int X[]){
    sort(X,X+L);
    bignum val={{0}};
    for (int i=0;i<L;i++)
        for (int j=(i?X[i-1]:0);j<X[i];j++)
            val=val+calc(255-j,L-i-1);
    while (N--){
        auto [q,r]=val/256;
        output(r);
        val=q;
    }
}

Compilation message

encoder.cpp: In function 'bignum operator+(bignum, bignum)':
encoder.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator-(bignum, bignum)':
encoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
encoder.cpp: In function 'bignum operator*(bignum, int)':
encoder.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~

decoder.cpp: In function 'bignum operator+(bignum, bignum)':
decoder.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
decoder.cpp: In function 'bignum operator-(bignum, bignum)':
decoder.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<a.d.size();i++){
      |                  ~^~~~~~~~~~~
decoder.cpp: At global scope:
decoder.cpp:33:15: warning: 'bignum operator-(bignum, bignum)' defined but not used [-Wunused-function]
   33 | static bignum operator -(bignum a, bignum b){
      |               ^~~~~~~~
decoder.cpp:9:15: warning: 'bignum f(int)' defined but not used [-Wunused-function]
    9 | static bignum f(int x){
      |               ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7456 KB Output is correct
2 Correct 11 ms 7716 KB Output is correct
3 Correct 13 ms 7964 KB Output is correct
4 Correct 16 ms 7968 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7444 KB Output is correct
2 Correct 10 ms 7716 KB Output is correct
3 Correct 15 ms 7964 KB Output is correct
4 Correct 15 ms 7956 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7440 KB Output is correct
2 Correct 14 ms 8184 KB Output is correct
3 Correct 17 ms 9000 KB Output is correct
4 Correct 24 ms 11312 KB Output is correct
5 Correct 27 ms 11568 KB Output is correct
6 Correct 32 ms 12112 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7964 KB Output is correct - P = 1.750000
2 Correct 37 ms 11904 KB Output is correct - P = 2.437500
3 Correct 31 ms 12528 KB Output is correct - P = 2.484848
4 Correct 54 ms 22256 KB Output is correct - P = 3.300000
5 Correct 103 ms 31744 KB Output is correct - P = 3.850000
6 Correct 98 ms 35320 KB Output is correct - P = 4.031746
7 Correct 87 ms 36736 KB Output is correct - P = 4.093750