Submission #62559382

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenw {
    int n;
    vector<int> tree;
    Fenw(int n): n(n), tree(n+1, 0) { }
    void init() {
        for (int i = 1; i <= n; i++) tree[i] = 0;
    }
    void update(int i, int delta){
        for(; i <= n; i += i & -i)
            tree[i] += delta;
    }
    int sum(int i){
        int s = 0;
        for(; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Fenw {
    int n;
    vector<int> tree;
    Fenw(int n): n(n), tree(n+1, 0) { }
    void init() {
        for (int i = 1; i <= n; i++) tree[i] = 0;
    }
    void update(int i, int delta){
        for(; i <= n; i += i & -i)
            tree[i] += delta;
    }
    int sum(int i){
        int s = 0;
        for(; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }
    // kth 1-indexed free position
    int findKth(int k){
        int pos = 0;
        for (int bit = 1 << 20; bit > 0; bit >>= 1){
            int nextPos = pos + bit;
            if (nextPos <= n && tree[nextPos] < k) {
                k -= tree[nextPos];
                pos = nextPos;
            }
        }
        return pos + 1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> P(N+1);
    for (int i = 1; i <= N; i++){
        cin >> P[i];
    }
    
    // BIT(1-indexed)で初期状態は全て空（1が埋まっているとみなす）
    Fenw fenw(N);
    for (int i = 1; i <= N; i++){
        fenw.update(i, 1);
    }
    
    vector<int> res(N+1, 0);
    // i = N downto 1 で、P[i] 番目の空き位置に i を配置する
    for (int i = N; i >= 1; i--){
        int k = P[i];
        int pos = fenw.findKth(k);
        res[pos] = i;
        fenw.update(pos, -1); // pos を利用済みにする
    }
    
    // 1-indexedの位置順に出力
    for (int i = 1; i <= N; i++){
        cout << res[i] << (i==N ? "\n" : " ");
    }
    
    return 0;
}

Submission Info

Judge Result