This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
const int MAXN = 70005;
const int S = 300;
int n;
llint d[MAXN], sol[MAXN], fen[MAXN], p[MAXN];
string prosli, curr;
llint m1 = 1000000009, b1 = 10;
deque <llint> v[S + 5];
unordered_set <llint> st[S + 5];
llint ofs[S + 5];
void ubaci (int x, int k) {
for (; x < MAXN; x += x&-x) fen[x] += k;
}
int kth (int k) {
int x = 0, curr = 0;
for (int pot = 16; pot >= 0; pot--) {
if (x + (1<<pot) < MAXN && curr + fen[x + (1<<pot)] < k) {
x += (1 << pot);
curr += fen[x];
}
}
return x+1;
}
void sub (string & a, string & b, int ind) {
int lena = a.size(), lenb = b.size();
string s = a;
int carry = 0;
int pos = lena - 1;
for (int i=lena-1; i>=0; i--) {
int x = a[i] - '0', y, val;
if (lenb - lena + i >= 0) y = b[lenb - lena + i] - '0'; else y = 0;
val = x - y - carry;
carry = 0;
if (val < 0) carry = 1, val += 10;
s[pos] = val + '0';
pos--;
}
llint h = 0;
for (int i=0; i<lena; i++) {
h = (h * b1 + s[i] - '0') % m1;
}
d[ind] = h;
}
inline llint add (llint a, llint b) {
a += b;
if (a >= m1) a -= m1;
return a;
}
int ubaci (llint val) {
int res = 0;
int lim = (n + S - 1) / S + 1;
for (int i=0; i<=lim; i++) {
llint pise = val - 1 - ofs[i];
if (pise < 0) pise += m1;
if (st[i].find(pise) != st[i].end()) {
st[i].clear();
deque <llint> e;
bool naso = 0;
for (int j=0; j<v[i].size(); j++) {
if (naso) {
llint dodaj = add(v[i] [j], val);
e.push_back(dodaj);
st[i].insert(dodaj);
} else {
e.push_back(v[i] [j]);
st[i].insert(v[i] [j]);
}
if (!naso && v[i] [j] == pise) {
naso = 1;
res = S * i + j;
pise = add(pise, val);
e.push_back(pise);
st[i].insert(pise);
}
}
v[i] = e;
for (int j = i+1; j <= lim; j++) {
ofs[j] = add(ofs[j], val);
}
int curr = i;
while (v[curr].size() > S) {
llint kraj = v[curr].back();
st[curr].erase(kraj);
v[curr].pop_back();
llint novo = (kraj + ofs[curr] - ofs[curr+1] + m1) % m1;
v[curr+1].push_front(novo);
st[curr+1].insert(novo);
curr++;
}
break;
}
}
return res;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
v[0].push_back(0);
st[0].insert(0);
prosli = "0";
for (int i=1; i<=n; i++) {
cin >> curr;
sub(curr, prosli, i);
swap(prosli, curr);
sol[i] = ubaci(d[i]);
}
for (int i=1; i<=n; i++) {
ubaci(i, 1);
}
for (int i=n; i>=1; i--) {
p[i] = kth(sol[i] + 1);
ubaci(p[i], -1);
}
for (int i=1; i<=n; i++) {
cout << p[i] << " ";
}
return 0;
}
Compilation message (stderr)
permutation.cpp: In function 'int ubaci(llint)':
permutation.cpp:70:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<v[i].size(); j++) {
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |