#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 70000
#define B 10
#define L 1
int max(int a, int b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
void print(long long *aa, int n) {
int i;
if (n == 0) {
printf("0\n");
return;
}
i = n - 1;
while (i > 0 && aa[i] == 0)
i--;
printf("%lld", aa[i]);
while (i--)
printf("%018lld", aa[i]);
}
long long *add(long long *aa, int n, long long *bb, int m, int *n1) {
long long *cc;
int n_, i;
if (n == 0 && m == 0) {
*n1 = 0;
return NULL;
}
n_ = max(n, m);
cc = (long long *) malloc(n_ * sizeof *cc);
for (i = 0; i < n_; i++)
cc[i] = (i < n ? aa[i] : 0) + (i < m ? bb[i] : 0);
for (i = 0; i + 1 < n_; i++)
if (cc[i] >= B)
cc[i] -= B, cc[i + 1]++;
if (cc[n_ - 1] >= B) {
cc = (long long *) realloc(cc, n_ * 2 * sizeof *cc);
cc[n_ - 1] -= B, cc[n_]++;
n_ *= 2;
}
*n1 = n_;
return cc;
}
void subtract(long long *aa, int n, long long *bb, int m, int *n1) {
int n_, i;
for (i = 0; i < m; i++)
aa[i] -= bb[i];
for (i = 0; i < n; i++)
if (aa[i] < 0)
aa[i] += B, aa[i + 1]--;
n_ = n;
while (n_ >= 2 && aa[n_ - 1] == 0)
n_--;
while ((n_ & n_ - 1) != 0)
n_++;
if (n_ != n)
aa = (long long *) realloc(aa, n_ * sizeof *aa);
*n1 = n_;
}
int compare(long long *aa, int n, long long *bb, int m) {
int h;
if (n != m)
return n - m;
for (h = n - 1; h >= 0; h--)
if (aa[h] != bb[h])
return aa[h] < bb[h] ? -1 : 1;
return 0;
}
long long *aa[N]; int nn[N];
int zz[N + 1], ii[N + 1], ll[N + 1], rr[N + 1]; long long *ss[N + 1]; int nn_[N + 1];
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i;
ss[_] = (long long *) malloc(nn[i] * sizeof *ss[_]);
memcpy(ss[_], aa[i], (nn_[_] = nn[i]) * sizeof *aa[i]);
return _++;
}
void pul(int u) {
int l, r;
long long *tmp;
int n;
l = ll[u], r = rr[u];
if (ss[u])
free(ss[u]);
tmp = add(ss[l], nn_[l], ss[r], nn_[r], &n);
ss[u] = add(tmp, n, aa[ii[u]], nn[ii[u]], &nn_[u]);
if (tmp)
free(tmp);
}
long long *aa_; int n_, u_, l_, r_;
void split(int u) {
if (u == 0) {
l_ = 0, r_ = 0;
return;
}
if (compare(aa_, n_, ss[ll[u]], nn_[ll[u]]) <= 0) {
split(ll[u]);
ll[u] = r_, r_ = u;
} else {
subtract(aa_, n_, ss[ll[u]], nn_[ll[u]], &n_);
if (compare(aa_, n_, aa[ii[u]], nn[ii[u]]) <= 0) {
l_ = ll[u], r_ = u;
ll[u] = 0;
} else {
subtract(aa_, n_, aa[ii[u]], nn[ii[u]], &n_);
split(rr[u]);
rr[u] = l_, l_ = u;
}
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v), pul(u);
return u;
} else {
ll[v] = merge(u, ll[v]), pul(v);
return v;
}
}
int pp[N], p;
void dfs(int u) {
if (u == 0)
return;
dfs(ll[u]), pp[ii[u]] = p++, dfs(rr[u]);
}
int main() {
int n, g, gl, gr, h, i;
scanf("%d", &n);
for (i = 0; i < n; i++) {
static char cc[N + 1];
int l;
scanf("%s", cc), l = strlen(cc);
nn[i] = (l + L - 1) / L;
while ((nn[i] & nn[i] - 1) != 0)
nn[i]++;
aa[i] = (long long *) malloc(nn[i] * sizeof *aa[i]);
for (h = 0; h < nn[i]; h++) {
gl = max(l - (h + 1) * L, 0), gr = max(l - h * L, 0);
aa[i][h] = 0;
for (g = gl; g < gr; g++)
aa[i][h] = aa[i][h] * 10 + (cc[g] - '0');
}
}
for (i = n - 1; i > 0; i--)
subtract(aa[i], nn[i], aa[i - 1], nn[i - 1], &nn[i]);
for (i = 0; i < n; i++) {
aa_ = (long long *) malloc(nn[i] * sizeof *aa_);
memcpy(aa_, aa[i], (n_ = nn[i]) * sizeof *aa);
split(u_);
u_ = merge(merge(l_, node(i)), r_);
}
dfs(u_);
for (i = 0; i < n; i++)
printf("%d ", pp[i] + 1);
printf("\n");
return 0;
}
Compilation message
permutation.cpp: In function 'void subtract(long long int*, int, long long int*, int, int*)':
permutation.cpp:67:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
67 | while ((n_ & n_ - 1) != 0)
| ~~~^~~
permutation.cpp: In function 'int main()':
permutation.cpp:168:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
168 | while ((nn[i] & nn[i] - 1) != 0)
| ~~~~~~^~~
permutation.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
permutation.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%s", cc), l = strlen(cc);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
