#include "bits/stdc++.h"
using namespace std;
int n;
int p[100010];
int q[100010];
int a[100010];
typedef pair <long long, int> pii;
const long long inf = 1e18;
pii t[100010 * 4];
int prop[100010 * 4];
void pushdown(int c) {
int l = c << 1;
int r = l + 1;
t[l].first += prop[c];
t[r].first += prop[c];
prop[l] += prop[c];
prop[r] += prop[c];
prop[c] = 0;
}
void update(int x, int y, long long val, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) {
t[c].first += val;
prop[c] += val;
return ;
}
if(y < b || e < x) return ;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
update(x, y, val, l, b, m);
update(x, y, val, r, m + 1, e);
t[c] = min(t[l], t[r]);
}
void build(int c = 1, int b = 1, int e = n) {
if(b == e) {
t[c].first = q[b];
t[c].second = -b;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
build(l, b, m);
build(r, m + 1, e);
t[c] = min(t[l], t[r]);
}
int main(int argc, char const *argv[])
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", p + i);
}
for(int i = n; i >= 1; i--) {
p[i] -= p[i - 1];
}
for(int i = 1; i <= n; i++) {
q[i] = p[i];
}
build();
int cur = 0;
for(int i = 1; i <= n; i++) {
int idx = -t[1].second;
update(idx, n, -q[idx]);
update(idx, idx, inf);
a[idx] = ++cur;
}
for(int i = 1; i <= n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Compilation message
permutation.cpp: In function 'int main(int, const char**)':
permutation.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
permutation.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", p + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
