#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#define ll long long
//#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pb push_back
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define pow2(x) (1ll<<(x))
#define inf 0x3f3f3f3f3f3f3f3f
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif
const int maxn=70005,mod=1000000007;
#define num vector<int>
int n,val[maxn*4],minid[maxn*4],ans[maxn];
num a[maxn],minn[maxn*4],tag[maxn*4];
void noob(num& x){
if(x.empty()){
x.pb(0);
return;
}
rep(sz(x)-1){
while(x[i]>=100000000) x[i]-=100000000,x[i]++;
while(x[i]<0) x[i]+=100000000,x[i+1]--;
}
while(x.back()>=100000000||x.back()<=-100000000){
x.pb(x.back()/100000000);
x[sz(x)-2]%=100000000;
}
while(sz(x)>1&&x.back()==0) x.pop_back();
}
void ri(num& x){
x.clear();
string str;
cin >> str;
reverse(all(str));
while(sz(str)%8) str+='0';
for(int i=0; i<sz(str); i+=8){
x.pb(0);
rep3(j,i+7,i) x.back()=x.back()*10+(str[j]^'0');
}
}
num operator +(const num& x, const num& y){
int k=max(sz(x),sz(y));
num res(k);
rep(sz(x)) res[i]+=x[i];
rep(sz(y)) res[i]+=y[i];
noob(res);
return res;
}
num operator -(const num& x, const num& y){
int k=max(sz(x),sz(y));
num res(k);
rep(sz(x)) res[i]+=x[i];
rep(sz(y)) res[i]-=y[i];
noob(res);
return res;
}
num operator +=(num& x, const num& y){
int k=max(sz(x),sz(y));
x.resize(k);
rep(sz(y)) x[i]+=y[i];
noob(x);
return x;
}
bool operator <(const num& x, const num& y){
if(x.back()<0&&y.back()>=0) return true;
if(y.back()<0&&x.back()>=0) return false;
bool flag=0;
if(x.back()<0) flag=1;
if(sz(x)<sz(y)) return 1^flag;
if(sz(y)<sz(x)) return flag;
rep3(i,sz(x)-1,0){
if(x[i]<y[i]) return true;
if(x[i]>y[i]) return false;
}
return false;
}
void pull(int k){
val[k]=val[k<<1]+val[k<<1|1];
if(!val[k<<1]) return minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1],void();
if(!val[k<<1|1]) return minn[k]=minn[k<<1],minid[k]=minid[k<<1],void();
if(minn[k<<1]<minn[k<<1|1]) minn[k]=minn[k<<1],minid[k]=minid[k<<1];
else minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1];
}
void push(int k, int l, int r){
if(l!=r){
minn[k<<1]+=tag[k];
minn[k<<1|1]+=tag[k];
tag[k<<1]+=tag[k];
tag[k<<1|1]+=tag[k];
}
tag[k]=num(1);
}
void build(int k, int l, int r){
if(l==r){
minn[k]=a[l];
minid[k]=l;
val[k]=1;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
pull(k);
}
void modify(int k, int l, int r, int ql, int qr, num& x){
if(l>qr||r<ql) return;
if(ql<=l&&qr>=r){
minn[k]+=x,tag[k]+=x;
return;
}
int mid=l+r>>1;
push(k,l,r);
modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x);
pull(k);
}
void modify2(int k, int l, int r, int p){
if(l==r){
val[k]--;
return;
}
int mid=l+r>>1;
push(k,l,r);
if(p<=mid) modify2(k<<1,l,mid,p);
else modify2(k<<1|1,mid+1,r,p);
pull(k);
}
void print(int k, int l, int r){
bug(k,l,r,minid[k]);
for(auto i: minn[k]) bug(i);
if(l==r) return;
push(k,l,r);
int mid=l+r>>1;
print(k<<1,l,mid),print(k<<1|1,mid+1,r);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n;
rep(n) ri(a[i]);
rep(n) for(auto j: a[i]) bug(i,j);
rep3(i,n-1,1) a[i]=a[i]-a[i-1];
rep(n) for(auto j: a[i]) bug(i,j);
build(1,0,n-1);
rep(n){
int x=minid[1];
ans[x]=i+1;
bug(x);
modify2(1,0,n-1,x);
num tmp(1);
tmp=tmp-a[x];
modify(1,0,n-1,x+1,n-1,tmp);
}
rep(n) cout << ans[i] << ' ';
cout << "\n";
}
Compilation message
permutation.cpp: In function 'void build(int, int, int)':
permutation.cpp:126:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void modify(int, int, int, int, int, std::vector<int>&)':
permutation.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
137 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void modify2(int, int, int, int)':
permutation.cpp:148:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
148 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void print(int, int, int)':
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
24 | #define bug(...) 49
| ^~
permutation.cpp:156:5: note: in expansion of macro 'bug'
156 | bug(k,l,r,minid[k]);
| ^~~
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
24 | #define bug(...) 49
| ^~
permutation.cpp:157:26: note: in expansion of macro 'bug'
157 | for(auto i: minn[k]) bug(i);
| ^~~
permutation.cpp:157:14: warning: unused variable 'i' [-Wunused-variable]
157 | for(auto i: minn[k]) bug(i);
| ^
permutation.cpp:160:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
160 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'int main()':
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
24 | #define bug(...) 49
| ^~
permutation.cpp:168:30: note: in expansion of macro 'bug'
168 | rep(n) for(auto j: a[i]) bug(i,j);
| ^~~
permutation.cpp:168:21: warning: unused variable 'j' [-Wunused-variable]
168 | rep(n) for(auto j: a[i]) bug(i,j);
| ^
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
24 | #define bug(...) 49
| ^~
permutation.cpp:170:30: note: in expansion of macro 'bug'
170 | rep(n) for(auto j: a[i]) bug(i,j);
| ^~~
permutation.cpp:170:21: warning: unused variable 'j' [-Wunused-variable]
170 | rep(n) for(auto j: a[i]) bug(i,j);
| ^
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
24 | #define bug(...) 49
| ^~
permutation.cpp:175:9: note: in expansion of macro 'bug'
175 | bug(x);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15052 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
15192 KB |
Output isn't correct |
