#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v[70005];
int p[70005];
vector<int> getBig(string s) {
vector<int> r;
for(auto it = s.rbegin(); it != s.rend(); ++it) {
r.push_back(*it - '0');
}
return r;
}
void printBig(vector<int> x) {
if(x.size() == 0) {
cout<<'0';
}
for(auto it = x.rbegin(); it != x.rend(); ++it) {
cout<<*it;
}
}
vector<int> addBig(vector<int> a, vector<int> b) {
if(a.size() < b.size()) {
swap(a, b);
}
a.push_back(0);
while(b.size() < a.size()) {
b.push_back(0);
}
for(int i=0; i<a.size(); ++i) {
a[i] += b[i];
if(a[i] > 10) {
++a[i+1];
a[i] -= 10;
}
}
while(!a.empty() && a.back() == 0) {
a.pop_back();
}
return a;
}
vector<int> substractBig(vector<int> a, vector<int> b) {
while(b.size() < a.size()) {
b.push_back(0);
}
for(int i=0; i<a.size(); ++i) {
a[i] -= b[i];
if(a[i] < 0) {
--a[i+1];
a[i] += 10;
}
}
while(!a.empty() && a.back() == 0) {
a.pop_back();
}
return a;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i=1; i<=n; ++i) {
string str; cin>>str;
v[i] = getBig(str);
}
for(int i=n; i>1; --i) {
v[i] = substractBig(v[i], v[i-1]);
}
p[1] = 1;
vector<int> ord = {1};
for(int i=2; i<=n; ++i) {
vector<int> sum = substractBig(v[i], getBig("1"));
int j = 0;
while(sum.size() != 0) {
sum = substractBig(sum, v[ord[j]]);
++j;
}
p[i] = j + 1;
for(int k=j; k<ord.size(); ++k) {
++p[ord[k]];
}
ord.insert(ord.begin() + j, i);
}
for(int i=1; i<=n; ++i) {
cout<<p[i]<<' ';
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
