#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000009
#define N 70005
#define MAX 10000006
#define LOG 30
#define KOK 275
using namespace std;
int n,gsz,cache,prevv,len;
int lazy[KOK],sz[KOK],ans[N];
ii GR[KOK][KOK*2];
ii ar[N];
char s[N];
unordered_map<int,bool> MP[KOK];
int get_hash() {
int res=0;
for(int i=1;i<=len;i++) res=(1ll*res*10+(s[i]-'0'))%MOD;
return res;
}
void rebuild() {
int cnt=0;
cache=0;
for(int i=1;i<=gsz;i++) {
for(int j=1;j<=sz[i];j++) {
GR[i][j].st=(GR[i][j].st+lazy[i])%MOD;
ar[++cnt]=GR[i][j];
}
MP[i].clear();
}
gsz=0;
for(int i=1;i<=cnt;i+=KOK) {
++gsz;
sz[gsz]=0;
lazy[gsz]=0;
for(int j=i;j<=min(i+KOK-1,cnt);j++) {
GR[gsz][j]=ar[j];
sz[gsz]++;
MP[gsz][ar[j].st]=1;
}
}
}
void push_here(int pos,int val,int ith,int gr) {
MP[gr].clear();
for(int i=1;i<=sz[gr];i++) {
GR[gr][i].st=(GR[gr][i].st+lazy[gr])%MOD;
}
lazy[gr]=0;
for(int i=sz[gr];i>pos;i--) {
GR[gr][i+1]=GR[gr][i];
GR[gr][i+1].st=(GR[gr][i+1].st+val)%MOD;
}
GR[gr][pos+1]={(val+GR[gr][pos].st)%MOD,ith};
sz[gr]++;
for(int i=1;i<=sz[gr];i++) MP[gr][GR[gr][i].st]=1;
}
void insert_here(int val,int ith,int gr) {
for(int i=1;i<=sz[gr];i++) {
if((GR[gr][i].st+1+lazy[gr])%MOD==val) {
push_here(i,val,ith,gr);
return ;
}
}
}
void insert(int val,int ith) {
cache++;
for(int i=1;i<=gsz;i++) {
int want=(val-lazy[i]-1+MOD)%MOD;
if(MP[i].count(want)) {
insert_here(val,ith,i);
for(int j=i+1;j<=gsz;j++) lazy[j]=(lazy[j]+val)%MOD;
if(cache==KOK-5) {
rebuild();
}
return ;
}
}
}
int main() {
//freopen("input.txt","r",stdin);
scanf("%d",&n);
gsz=1;
GR[1][1]={0,0};
sz[1]=1;
MP[1][0]=1;
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
len=strlen(s+1);
int num=get_hash();
int no=(num-prevv+MOD)%MOD;
prevv=num;
insert(no,i);
}
int val=-1;
for(int i=1;i<=gsz;i++) {
for(int j=1;j<=sz[gsz];j++) {
ans[GR[i][j].nd]=++val;
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}
Compilation message
permutation.cpp: In function 'int main()':
permutation.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
permutation.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
10 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
