#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;
};
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 0;
}
bool operator<=(bigInt x, bigInt y)
{
if(x==y || x<y)
return 1;
return 0;
}
bigInt operator-(bigInt x, bigInt y)///return x-y
{
bigInt sc;
if(x<y)
{
return 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;
}
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;
}
sum[b].cif.clear();
for(int i=0;i<cntv;i++)
sum[b].cif.push_back(newv[i]);
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;
insereaza(unde, i, aux);continue;
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 'bool operator<(bigInt, bigInt)':
permutation.cpp:24:18: 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<x.cif.size();i++)
| ~^~~~~~~~~~~~~
permutation.cpp: In function 'bigInt 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:49:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if(i<y.cif.size() && newx.cif[i] >= y.cif[i])
| ~^~~~~~~~~~~~~
permutation.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | else if(i>=y.cif.size())
| ~^~~~~~~~~~~~~~
permutation.cpp: In function 'void balance_buckets()':
permutation.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0;i<buckets.size();i++)
| ~^~~~~~~~~~~~~~~
permutation.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0;j<buckets[i].v.size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0;i<ramas.size();i+=bucket_size)
| ~^~~~~~~~~~~~~
permutation.cpp: In function 'void insereaza(int, int, bigInt)':
permutation.cpp:109:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
109 | if(sum[b].cif.size()>lim)
| ~~~~~~~~~~~~~~~~~^~~~
permutation.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(i<sum[b].cif.size())
| ~^~~~~~~~~~~~~~~~~~
permutation.cpp:115:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | if(i<q[poz].cif.size())
| ~^~~~~~~~~~~~~~~~~~
permutation.cpp:131:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i=0;i<buckets[b].v.size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:171:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for(int j=0;j<buckets.size();j++)
| ~^~~~~~~~~~~~~~~
permutation.cpp:170:14: warning: variable 'bl' set but not used [-Wunused-but-set-variable]
170 | bool bl=0;
| ^~
permutation.cpp:191:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for(int i=0;i<buckets.size();i++)
| ~^~~~~~~~~~~~~~~
permutation.cpp:193:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | for(int j=0;j<buckets[i].v.size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:157:9: warning: unused variable 'procent' [-Wunused-variable]
157 | int procent=0;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
