Submission #688480

#	Time	Username	Problem	Language	Result	Execution time	Memory
688480		alexdd	Permutation Recovery (info1cup17_permutation)	C++17	60 / 100	4089 ms	56464 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
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() && x.cif[i] >= y.cif[i])
            sc.cif.push_back(x.cif[i] - y.cif[i]);
        else if(i>=y.cif.size())
            sc.cif.push_back(x.cif[i]);
        else
        {
            int j=i+1;
            while(x.cif[j]==0)
                x.cif[j++]=9;
            x.cif[j]--;
            sc.cif.push_back(10+x.cif[i]-y.cif[i]);
        }
    }
    while(!sc.cif.empty() && sc.cif[sc.cif.size()-1]==0)
        sc.cif.pop_back();
    x = newx;
    return sc;
}
bigInt operator+(bigInt x, bigInt y)
{
    bigInt ad;
    int r=0;
    for(int i=0;i<max(x.cif.size(), y.cif.size());i++)
    {
        if(i<x.cif.size())
            r+=x.cif[i];
        if(i<y.cif.size())
            r+=y.cif[i];
        ad.cif.push_back(r%10);
        r/=10;
    }
    while(r>0)
    {
        ad.cif.push_back(r%10);
        r/=10;
    }
    return ad;
}
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=x.cif.size()-1;i>=0;i--)
    {
        if(x.cif[i]<y.cif[i])
            return 1;
        if(x.cif[i]>y.cif[i])
            return 0;
    }
    return 1;
}
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=x.cif.size()-1;i>=0;i--)
    {
        if(x.cif[i]<y.cif[i])
            return 1;
        if(x.cif[i]>y.cif[i])
            return 0;
    }
    return 0;
}
bool operator>(bigInt x, bigInt y)
{
    return y<x;
}
bigInt q[70001];
bigInt zer;
bigInt unu = {{1}};

struct bucket
{
    bigInt sum;
    vector<int> v;
};
bucket gol;



vector<bucket> buckets;
bigInt aint[70000];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = buckets[st].sum;
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = aint[nod*2]+aint[nod*2+1];
}
void upd(int nod, int st, int dr, int poz, bigInt newval)
{
    if(st==dr)
    {
        aint[nod]=newval;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newval);
    else
        upd(nod*2+1,mij+1,dr,poz,newval);
    aint[nod] = aint[nod*2]+aint[nod*2+1];
}
pair<int,bigInt> qry(int nod, int st, int dr, bigInt k)
{
    if(st==dr)
        return {st, k};
    int mij=(st+dr)/2;
    if(k<=aint[nod*2])
        return qry(nod*2,st,mij,k);
    else
        return qry(nod*2+1,mij+1,dr,k-aint[nod*2]);
}
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]);
            buckets[buckets.size()-1].sum = buckets[buckets.size()-1].sum + q[ramas[j]];
        }
    }
    build(1,0,buckets.size()-1);
}



void insereaza(int b, int poz, bigInt ramas)///O(marimea bucketului in care inserez)
{
    buckets[b].sum = buckets[b].sum + q[poz];
    upd(1,0,buckets.size()-1,b,buckets[b].sum);
    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 = 3000;
    bucket_size = 50;

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

    prec = zer;
    string s;
    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;
        pair<int,bigInt> cv = qry(1,0,buckets.size()-1,aux);
        unde = cv.first;
        aux = cv.second;
        insereaza(unde, i, aux);

        if(i<n && i%update_timer==0)
        {
            balance_buckets();
        }
    }

    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 (stderr)

permutation.cpp: In function 'bigInt operator-(bigInt, bigInt)':
permutation.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<x.cif.size();i++)
      |                 ~^~~~~~~~~~~~~
permutation.cpp:17:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         if(i<y.cif.size() && x.cif[i] >= y.cif[i])
      |            ~^~~~~~~~~~~~~
permutation.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         else if(i>=y.cif.size())
      |                 ~^~~~~~~~~~~~~~
permutation.cpp: In function 'bigInt operator+(bigInt, bigInt)':
permutation.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   39 |     for(int i=0;i<max(x.cif.size(), y.cif.size());i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(i<x.cif.size())
      |            ~^~~~~~~~~~~~~
permutation.cpp:43:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if(i<y.cif.size())
      |            ~^~~~~~~~~~~~~
permutation.cpp: In function 'void balance_buckets()':
permutation.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:151:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i=0;i<ramas.size();i+=bucket_size)
      |                 ~^~~~~~~~~~~~~
permutation.cpp: In function 'void insereaza(int, int, bigInt)':
permutation.cpp:171:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for(int i=0;i<buckets[b].v.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:220:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:222:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6