language: Ruby (ruby-1.9.3)
date: 232 days 0 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

# O(n(log(n))^2) solution for http://opc.iarcs.org.in/index.php/problems/FINDPERM
 
# Binary Indexed Tree (by Peter Fenwick)
# http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
class FenwickTree
  
  # Initialize array 1..n with 0s
  def initialize(n)
    @n = n
    @m = [0] * (n + 1)
  end
  
  # Add value v to cell i
  def add(i, v)
    while i <= @n
      @m[i] += v
      i += i & -i
    end
  end
  
  # Get sum on 1..i
  def sum(i)
    s = 0
    while i > 0
      s += @m[i]
      i -= i & -i
    end
    s
  end
  
  # Array size
  def n
    return @n
  end
  
end
 
# Classical binary search
# http://en.wikipedia.org/wiki/Binary_search_algorithm
class BinarySearch
 
  # Find lower index i such that ft.sum(i) == s
  def self.lower_bound(ft, s)
    l, r = 1, ft.n
    while l < r
      c = (l + r) / 2
      if ft.sum(c) < s
        l = c + 1
      else
        r = c
      end
    end
    l
  end
  
end
 
# Read input data
n = gets.to_i
q = gets.split.map &:to_i
 
# Initialize Fenwick tree
ft = FenwickTree.new(n)
1.upto(n) do |i|
  ft.add i, 1
end
 
# Find the answer
ans = [0] * n
(n - 1).downto(0) do |i|
  k = BinarySearch.lower_bound(ft, q[i] + 1)
  ans[n - k] = i + 1
  ft.add k, -1
end
puts ans.join(' ')