#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[290000];
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 = 500;
bucket_size = 1;
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
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++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| 5 |
Execution timed out |
4056 ms |
95480 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| 5 |
Execution timed out |
4056 ms |
95480 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| 5 |
Execution timed out |
4056 ms |
95480 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| 5 |
Execution timed out |
4056 ms |
95480 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
64 ms |
9576 KB |
Output is correct |
| 4 |
Correct |
105 ms |
9400 KB |
Output is correct |
| 5 |
Execution timed out |
4056 ms |
95480 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
