#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const long long mod = (long long) 1e9+9;
const int MAXN = (int) 3e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
ll d[MAXN];
ll q[MAXN];
const ll bs = 300;
unordered_map<int, int> mp[MAXN];
int Dec[MAXN];
int ans[MAXN];
int del[MAXN];
int pw[MAXN][10];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
#ifdef Local
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
#endif
cin>>n;
pw[0][1] = 1;
for(int i = 0; i <= 100000; i++){
pw[i][0] = 0;
if(i != 0)
pw[i][1] = pw[i - 1][1]*10%mod;
for(int j = 2; j < 10; j++){
pw[i][j] = pw[i][1]*j%mod;
}
}
for(int i = 0; i < n; i++){
string s;
cin>>s;
reverse(s.begin(), s.end());
int cnt = 0;
for(char c: s){
int cur = c - '0';
del[i] += pw[cnt][cur];
if(del[i] >= mod) del[i] -= mod;
cnt++;
}
}
ll bc = (n + bs - 1) / bs;
for(ll i = 0; i < bc; i++){
for(ll j = i*bs; j < min(n, (i + 1)*bs); j++){
q[j] = del[j] - (j == 0 ? 0 : del[j - 1]);
if(q[j] < 0) q[j] += mod;
mp[i][q[j]]++;
//cerr<<q[j]<<endl;
}
}
for(ll i = 1; i <= n; i++){
ll curB = bc - 1;
while(mp[curB][(1 + Dec[curB])%mod] == 0){
curB--;
assert(curB != -1);
}
if(curB < 0) break;
ll idx = -1;
for(ll j = min(n - 1, (curB + 1)*bs - 1); j >= curB*bs; j--){
if(ans[j]) continue;
if(q[j] == (1 + Dec[curB])%mod){
ans[j] = i;
mp[curB].clear();
idx = j;
break;
}
}
ll deg = 0;
for(ll j = bs*curB; j < min(bs*(curB + 1), n); j++){
if(ans[j]){
if(j == idx){
deg = del[j] - (j == 0 ? 0 : del[j - 1]);
if(deg < 0) deg += mod;
}
continue;
}
q[j] -= deg;
if(q[j] < 0) q[j] += mod;
mp[curB][q[j]]++;
}
for(ll j = curB + 1; j < bc; j++){
Dec[j] += deg;
if(Dec[j] >= mod) Dec[j] -= mod;
}
}
for(ll i = 0; i < n; i++)
cout<<ans[i]<<" ";
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
41848 KB |
Execution killed with signal 11 |
