oj.uz

Submission #688449

# Submission time Handle Problem Language Result Execution time Memory
688449 2023-01-27T13:14:25 Z alexdd Permutation Recovery (info1cup17_permutation) C++17
43 / 100
 4000 ms 5016 KB 
#include<bits/stdc++.h>
using namespace std;
//ifstream fin("input05.in");
//#define cin fin
int bucket_size;
int update_timer;
int n;


struct bigInt
{
    vector<int> cif;
};
bigInt operator-(bigInt x, bigInt y)///return x-y
{
    bigInt sc;
    bigInt newx = x;
    for(int i=0;i<x.cif.size();i++)
    {
        if(i<y.cif.size() && newx.cif[i] >= y.cif[i])
            sc.cif.push_back(newx.cif[i] - y.cif[i]);
        else if(i>=y.cif.size())
            sc.cif.push_back(newx.cif[i]);
        else
        {
            int j=i+1;
            while(newx.cif[j]==0)
                newx.cif[j++]=9;
            newx.cif[j]--;
            sc.cif.push_back(10+newx.cif[i]-y.cif[i]);
        }
    }
    while(!sc.cif.empty() && sc.cif[sc.cif.size()-1]==0)
        sc.cif.pop_back();
    return sc;
}
bool operator==(bigInt x, bigInt y)
{
    return x.cif == y.cif;
}
bool operator<=(bigInt x, bigInt y)
{
    if(x.cif.size() < y.cif.size())
        return 1;
    if(x.cif.size() > y.cif.size())
        return 0;
    for(int i=0;i<x.cif.size();i++)
    {
        if(x.cif[i]<y.cif[i])
            return 1;
        if(x.cif[i]>y.cif[i])
            return 0;
    }
    return 1;
}
bigInt q[70001];
bigInt zer;
bigInt unu = {{1}};

void afisare(bigInt x)
{
    for(int i=x.cif.size()-1;i>=0;i--)
        cout<<x.cif[i];
}

struct bucket
{
    vector<int> v;
};
bucket gol;
bigInt sum[70001];
vector<bucket> buckets;
void balance_buckets()///O(n)
{
    vector<int> ramas;
    for(int i=0;i<buckets.size();i++)
        for(int j=0;j<buckets[i].v.size();j++)
            ramas.push_back(buckets[i].v[j]);
    buckets.clear();
    for(int i=0;i<ramas.size();i+=bucket_size)
    {
        buckets.push_back(gol);
        int limit = ramas.size()-1;
        limit = min(limit, i+bucket_size-1);
        for(int j=i;j<=limit;j++)
        {
            buckets[buckets.size()-1].v.push_back(ramas[j]);
           // sum[buckets.size()-1] += q[ramas[j]];
        }
    }
}

int newv[50001],cntv;

void insereaza(int b, int poz, bigInt ramas)///O(marimea bucketului in care inserez)
{
    cntv=0;
    int r=0,lim=q[poz].cif.size();
    if(sum[b].cif.size()>lim)
        lim = sum[b].cif.size();
    for(int i=0;i<lim;i++)
    {
        if(i<sum[b].cif.size())
            r+=sum[b].cif[i];
        if(i<q[poz].cif.size())
            r+=q[poz].cif[i];
        newv[cntv]=r%10;
        cntv++;
        r=r/10;
    }
    while(r>0)
    {
        newv[cntv]=r%10;
        cntv++;
        r=r/10;
    }
    //cout<<cntv<<"\n";
    //sum[b].cif = newv;
    sum[b].cif.clear();
    for(int i=0;i<cntv;i++)
    {
        //cout<<newv[i]<<" ";
        //sum[b].cif.push_back(newv[i]);
        sum[b].cif.push_back(0);
    }
    //cout<<"\n";

    for(int i=0;i<buckets[b].v.size();i++)
    {
        if(ramas==zer)
        {
            buckets[b].v.insert(buckets[b].v.begin()+i, poz);
            return;
        }
        ramas = ramas - q[buckets[b].v[i]];
    }
    buckets[b].v.insert(buckets[b].v.end(), poz);
}

int rez[70001];
signed main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;

    update_timer = 500;
    bucket_size = 100;

    buckets.push_back(gol);
    bigInt prec, ceva;

    prec = zer;
    string s;
    int procent=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=s.size()-1;j>=0;j--)
            q[i].cif.push_back(s[j]-'0');
        ceva = q[i];
        q[i] = q[i] - prec;
        prec = ceva;

        bigInt aux = q[i] - unu;
        int unde = 0;
        bool bl=0;
        for(int j=0;j<buckets.size();j++)
        {
            unde = j;
            if(aux <= sum[j])
            {
                bl=1;
                break;
            }
            aux = aux - sum[j];
        }

        insereaza(unde, i, aux);

        if(i<n && i%update_timer==0)
        {
            //balance_buckets();
        }
    }
    //return 0;
    int cate=0;
    for(int i=0;i<buckets.size();i++)
    {
        for(int j=0;j<buckets[i].v.size();j++)
        {
            cate++;
            rez[buckets[i].v[j]]=cate;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<rez[i]<<" ";
    return 0;
}

Compilation message

permutation.cpp: In function 'bigInt operator-(bigInt, bigInt)':
permutation.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<x.cif.size();i++)
      |                 ~^~~~~~~~~~~~~
permutation.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(i<y.cif.size() && newx.cif[i] >= y.cif[i])
      |            ~^~~~~~~~~~~~~
permutation.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         else if(i>=y.cif.size())
      |                 ~^~~~~~~~~~~~~~
permutation.cpp: In function 'bool operator<=(bigInt, bigInt)':
permutation.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<x.cif.size();i++)
      |                 ~^~~~~~~~~~~~~
permutation.cpp: In function 'void balance_buckets()':
permutation.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<ramas.size();i+=bucket_size)
      |                 ~^~~~~~~~~~~~~
permutation.cpp: In function 'void insereaza(int, int, bigInt)':
permutation.cpp:99:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |     if(sum[b].cif.size()>lim)
      |        ~~~~~~~~~~~~~~~~~^~~~
permutation.cpp:103:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         if(i<sum[b].cif.size())
      |            ~^~~~~~~~~~~~~~~~~~
permutation.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(i<q[poz].cif.size())
      |            ~^~~~~~~~~~~~~~~~~~
permutation.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=0;i<buckets[b].v.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for(int j=0;j<buckets.size();j++)
      |                     ~^~~~~~~~~~~~~~~
permutation.cpp:166:14: warning: variable 'bl' set but not used [-Wunused-but-set-variable]
  166 |         bool bl=0;
      |              ^~
permutation.cpp:187:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:189:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:154:9: warning: unused variable 'procent' [-Wunused-variable]
  154 |     int procent=0;
      |         ^~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct
5 Execution timed out 4022 ms 5016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct
5 Execution timed out 4022 ms 5016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct
5 Execution timed out 4022 ms 5016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct
5 Execution timed out 4022 ms 5016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 15 ms 3628 KB Output is correct
3 Correct 139 ms 3908 KB Output is correct
4 Correct 194 ms 3928 KB Output is correct
5 Execution timed out 4022 ms 5016 KB Time limit exceeded
6 Halted 0 ms 0 KB -