比赛 树状数组练习 评测结果 AAAAAAA
题目名称 Lost Cows 最终得分 100
用户昵称 LikableP 运行时间 0.026 s
代码语言 C++ 内存使用 1.46 MiB
提交时间 2025-06-11 21:21:46
显示代码纯文本
#include <cstdio>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
#define lowbit(x) (x & -x)

template <typename T> T read() {
	T res = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
	return res * f;
}

template <typename T> void write(T x, char ed = '\n') {
	if (x < 0) putchar('-'), x = -x;
	static int sta[16], top = 0;
	do {
		sta[++top] = x % 10;
		x /= 10;
	} while(x);
	while (top) {
		putchar(sta[top--] ^ 48);
	}
	putchar(ed);
}

const int MAXN = 1e5 + 10;

int n;
int a[MAXN], ans[MAXN];
int tree[MAXN];

void add(int x, int y) {
    for (; x <= n; x += lowbit(x)) tree[x] += y;
} 

int ask(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += tree[x];
    return res;
}

int main() {
    freopen("lostcows.in", "r", stdin);
    freopen("lostcows.out", "w", stdout);
    n = read<int>();
    for (int i = 1; i <= n; ++i) {
        add(i, 1);
        if (i > 1) a[i] = read<int>();
    }
    for (int i = n; i >= 1; --i) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (ask(mid) <= a[i]) {
                l = mid + 1; 
            } else {
                r = mid;
            }
        }
        ans[i] = r;
        add(r, -1);
    }
    for (int i = 1; i <= n; ++i) {
        write(ans[i]);
    }
    return 0;
}