#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#include <unordered_map>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset
using namespace std;
typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;
const int maxn = 70020;
const int maxk = 620;
const int MOd = 998244353;
const int K = 300;
int gs, a;
unordered_map<int,int> mp[maxk];
vector<ii> v[maxn];
int lazy[maxn];
int ans[maxn], ar[maxn];
int nex[maxn];
int add( int a, int b ) {
a += b;
a %= MOd;
if( a < 0 ) a += MOd;
return a;
}
int mul( int x, int y ) {
return (Lint)x*y % MOd;
}
void rebuild( int g ) {
int t = gs++;
nex[t] = nex[g];
nex[g] = t;
mp[g].clear();
vector<ii> v2;
for(int i=0;i<v[g].size();i++)
if( i < v[g].size()/2 ) v2.pb( v[g][i] );
else v[t].pb( v[g][i] );
v[g] = v2;
for(int i=0;i<v[g].size();i++) mp[g][ v[g][i].fi ] = 1;
for(int i=0;i<v[t].size();i++) mp[t][ v[t][i].fi ] = 1;
}
bool ins( int g, int x, int &loc ) {
//printf("asd %d -- %d\n",g,x);
if( !mp[g].count( add( x, -lazy[g] ) ) ) return false;
mp[g].clear();
vector<ii> v2;
int c = 0;
int val = 0;
for(int i=0;i<v[g].size();i++) {
v[g][i].fi = add( v[g][i].fi, lazy[g] );
if( c ) v[g][i].fi = add( v[g][i].fi, val );
mp[g][ v[g][i].fi ] = 1;
//printf("-- %d\n",v[g][i].fi);
v2.pb( v[g][i] );
if( v[g][i].fi == x ) { c = 1;
val = add( x, 1 );
int h = add( x, val );
v2.pb( ii( h, loc ) );
mp[g][h] = 1;
//printf("-- %d\n",h);
}
}
lazy[g] = 0;
for(int i=nex[g];i!=-1;i=nex[i])
lazy[i] = add( lazy[i], val );
v[g] = v2;
if( v[g].size() > K ) {
rebuild( g );
}
return true;
}
int main() {
//freopen("asd.in","r",stdin);
//freopen("output17.txt","w",stdout);
gs = 1;
scanf("%d",&a);
ar[0] = 0;
v[0].pb( ii( 0, 0 ) );
mp[0][0] = 1;
nex[0] = -1;
for(int i=1;i<=a;i++) {
string s;
cin >> s;
int x = 0;
for(int j=0;j<s.size();j++)
x = add( mul( x, 10 ), s[j]-'0' );
ar[i] = x;
int c = 0;
for(int j=0;j != -1;j=nex[j])
if( ins( j, add(ar[i],-ar[i-1]-1), i ) ) { c = 1; break; }
assert( c );
}
int cnt = -1;
for(int i=0;i<gs;i++)
for(int j=0;j<v[i].size();j++)
ans[ v[i][j].se ] = ++cnt;
for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");
return 0;
}
Compilation message
permutation.cpp: In function 'void rebuild(int)':
permutation.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[g].size();i++)
~^~~~~~~~~~~~
permutation.cpp:69:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( i < v[g].size()/2 ) v2.pb( v[g][i] );
~~^~~~~~~~~~~~~~~
permutation.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[g].size();i++) mp[g][ v[g][i].fi ] = 1;
~^~~~~~~~~~~~
permutation.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[t].size();i++) mp[t][ v[t][i].fi ] = 1;
~^~~~~~~~~~~~
permutation.cpp: In function 'bool ins(int, int, int&)':
permutation.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[g].size();i++) {
~^~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:126:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<s.size();j++)
~^~~~~~~~~
permutation.cpp:137:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
permutation.cpp:140:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");
^~~
permutation.cpp:140:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");
^~~~~~
permutation.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2104 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2104 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
