oj.uz

답안 #254346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254346 2020-07-29T21:23:26 Z MKopchev 앵무새 (IOI11_parrots) C++14
100 / 100
 200 ms 61936 KB 
#include "encoder.h"
#include "encoderlib.h"

#include<bits/stdc++.h>
using namespace std;

const int MX=600;

vector<int> COMB[MX][MX];
/*
int ARR[1000],p=0;
void send(int s)
{
    ARR[p]=s;
    p++;

    cout<<s<<endl;
}
void output(int s)
{
    cout<<"output "<<s<<endl;
}
*/
vector<int> normal(vector<int> a)
{
    int pos=0;

    while(pos<a.size())
    {
        if(0<=a[pos]&&a[pos]<=9)
        {
            pos++;
            continue;
        }

        if(pos+1==a.size())a.push_back(0);

        a[pos+1]+=a[pos]/10;
        a[pos]=a[pos]%10;

        if(a[pos]<0)
        {
            a[pos+1]--;
            a[pos]+=10;
        }

    }

    pos--;
    while(pos>0&&a[pos]==0)
    {
        a.pop_back();
        pos--;
    }
    return a;
}
vector<int> my_add(vector<int> a,vector<int> b)
{
    if(a.size()<b.size())swap(a,b);

    for(int i=0;i<b.size();i++)a[i]+=b[i];

    return normal(a);
}

vector<int> my_sub(vector<int> a,vector<int> b)
{
    for(int i=0;i<b.size();i++)a[i]-=b[i];

    return normal(a);
}

vector<int> my_mult(vector<int> a,int m)
{
    for(auto &k:a)k=k*m;
    return normal(a);
}

int my_mod(vector<int> a,int m)
{
    int ret=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        ret=ret*10+a[i];
        ret=ret%m;
    }
    return ret;
}

vector<int> my_div(vector<int> a,int m)
{
    int mem=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        mem=mem*10+a[i];

        a[i]=mem/m;

        mem=mem%m;
    }
    return normal(a);
}
vector<int> ask(int n,int k)
{
    if(k==n||k==0)return {1};
    if(COMB[n][k].size())return COMB[n][k];

    COMB[n][k]=my_add(ask(n-1,k),ask(n-1,k-1));

    return COMB[n][k];
}

bool more(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 0;
}

bool at_least(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 1;
}

void encode(int N, int M[])
{
    vector<int> which={0};
    for(int i=0;i<N;i++)
    {
        which=my_mult(which,256);
        which=my_add(which,{M[i]});
    }

    int sz=0;

    for(sz=0;more(ask(255+sz,sz),which)==0;sz++);

    //for(auto k:which)cout<<k;cout<<endl;
    //for(auto k:ask(255+sz,sz))cout<<k;cout<<endl;

    int lst=0;

    for(int i=1;i<=sz;i++)
    {
        int give=255-lst,pass=sz-i;

        vector<int> cur=ask(give+pass,pass);

        if(at_least(which,cur))
        {
            lst++;

            which=my_sub(which,cur);

            i--;
            continue;
        }

        //cout<<"sending "<<lst<<endl;
        send(lst);

        assert(0<=lst&&lst<=255);
    }

    //cout<<"sz= "<<sz<<endl;
}

#include "decoder.h"
#include "decoderlib.h"

#include<bits/stdc++.h>
using namespace std;

const int MX=600;

vector<int> COMB[MX][MX];
/*
int ARR[1000],p=0;
void send(int s)
{
    ARR[p]=s;
    p++;

    cout<<s<<endl;
}
void output(int s)
{
    cout<<"output "<<s<<endl;
}
*/
vector<int> normal(vector<int> a)
{
    int pos=0;

    while(pos<a.size())
    {
        if(0<=a[pos]&&a[pos]<=9)
        {
            pos++;
            continue;
        }

        if(pos+1==a.size())a.push_back(0);

        a[pos+1]+=a[pos]/10;
        a[pos]=a[pos]%10;

        if(a[pos]<0)
        {
            a[pos+1]--;
            a[pos]+=10;
        }

    }

    pos--;
    while(pos>0&&a[pos]==0)
    {
        a.pop_back();
        pos--;
    }
    return a;
}
vector<int> my_add(vector<int> a,vector<int> b)
{
    if(a.size()<b.size())swap(a,b);

    for(int i=0;i<b.size();i++)a[i]+=b[i];

    return normal(a);
}

vector<int> my_sub(vector<int> a,vector<int> b)
{
    for(int i=0;i<b.size();i++)a[i]-=b[i];

    return normal(a);
}

vector<int> my_mult(vector<int> a,int m)
{
    for(auto &k:a)k=k*m;
    return normal(a);
}

int my_mod(vector<int> a,int m)
{
    int ret=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        ret=ret*10+a[i];
        ret=ret%m;
    }
    return ret;
}

vector<int> my_div(vector<int> a,int m)
{
    int mem=0;

    for(int i=a.size()-1;i>=0;i--)
    {
        mem=mem*10+a[i];

        a[i]=mem/m;

        mem=mem%m;
    }
    return normal(a);
}
vector<int> ask(int n,int k)
{
    if(k==n||k==0)return {1};
    if(COMB[n][k].size())return COMB[n][k];

    COMB[n][k]=my_add(ask(n-1,k),ask(n-1,k-1));

    return COMB[n][k];
}

bool more(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 0;
}

bool at_least(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())return 1;
    if(a.size()<b.size())return 0;

    for(int i=a.size()-1;i>=0;i--)
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return 0;

    return 1;
}

void decode(int N, int L, int X[])
{
    vector<int> which={0};

    sort(X,X+L);

    int lst=0;

    for(int i=0;i<L;i++)
    {
        if(X[i]==lst)continue;

        int give=255-lst,pass=L-i-1;

        vector<int> cur=ask(give+pass,pass);

        which=my_add(which,cur);

        lst++;
        i--;
    }

    //for(auto k:which)cout<<k;cout<<endl;

    vector<int> outp={};
    for(int i=0;i<N;i++)outp.push_back(0);

    for(int i=N-1;i>=0;i--)
    {
        outp[i]=my_mod(which,256);

        which=my_div(which,256);
    }

    for(int i=0;i<N;i++)
        output(outp[i]);
}

Compilation message

encoder.cpp: In function 'std::vector<int> normal(std::vector<int>)':
encoder.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<a.size())
           ~~~^~~~~~~~~
encoder.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos+1==a.size())a.push_back(0);
            ~~~~~^~~~~~~~~~
encoder.cpp: In function 'std::vector<int> my_add(std::vector<int>, std::vector<int>)':
encoder.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]+=b[i];
                 ~^~~~~~~~~
encoder.cpp: In function 'std::vector<int> my_sub(std::vector<int>, std::vector<int>)':
encoder.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]-=b[i];
                 ~^~~~~~~~~

decoder.cpp: In function 'std::vector<int> normal(std::vector<int>)':
decoder.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<a.size())
           ~~~^~~~~~~~~
decoder.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos+1==a.size())a.push_back(0);
            ~~~~~^~~~~~~~~~
decoder.cpp: In function 'std::vector<int> my_add(std::vector<int>, std::vector<int>)':
decoder.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]+=b[i];
                 ~^~~~~~~~~
decoder.cpp: In function 'std::vector<int> my_sub(std::vector<int>, std::vector<int>)':
decoder.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)a[i]-=b[i];
                 ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 18300 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 18688 KB Output is correct
2 Correct 23 ms 18944 KB Output is correct
3 Correct 30 ms 19712 KB Output is correct
4 Correct 28 ms 19712 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 18688 KB Output is correct
2 Correct 22 ms 18944 KB Output is correct
3 Correct 27 ms 19712 KB Output is correct
4 Correct 31 ms 19712 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 18688 KB Output is correct
2 Correct 30 ms 19712 KB Output is correct
3 Correct 36 ms 20720 KB Output is correct
4 Correct 55 ms 24064 KB Output is correct
5 Correct 57 ms 24560 KB Output is correct
6 Correct 59 ms 25088 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 19712 KB Output is correct - P = 1.750000
2 Correct 60 ms 25072 KB Output is correct - P = 2.437500
3 Correct 63 ms 25600 KB Output is correct - P = 2.484848
4 Correct 122 ms 39920 KB Output is correct - P = 3.300000
5 Correct 177 ms 54512 KB Output is correct - P = 3.850000
6 Correct 200 ms 60144 KB Output is correct - P = 4.031746
7 Correct 197 ms 61936 KB Output is correct - P = 4.093750