# Orange lecture #12 - Beautiful People

# Đề bài
Có N người, mỗi người có sức mạnh S[i] và độ đẹp B[i].
Hai người i và j ghét nhau nếu S[i] <= S[j] và B[i] >= B[j], hoặc S[i] >= S[j] và B[i] <= B[j].

Ngược lại nếu cả 2 thuộc tính của một người lớn hơn 2 thuộc tính tương ứng của người kia thì cả 2 không ghét nhau (S[i] < S[j] & B[i] < B[j] hoặc S[i] > S[j] & B[i] > B[j]).

Chọn nhiều người tham gia bữa tiệc nhất sao cho không có 2 người nào được chọn ghét nhau.

### Input
- $N (2 \leq N \leq 10^5)$ - số người
- $N$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên $S[i]$ $B[i]$ $(1 \leq S[i], B[i] \leq 10^9)$

### Output
- M - số người được chọn
- M số nguyên trên một dòng - chỉ số của những người được chọn

**Ví dụ**

+-----------------+
|4                |
|1 1              |
|1 2              |
|2 1              |
|2 2              |
+-----------------+
|2                |
|1 4              |
+-----------------+

### **Giải thích ví dụ**

- Chọn người thứ nhất & người thứ 4

### **Hướng dẫn giải**

- Đưa về bài toán LIS: Sắp xếp S tăng dần, nếu cùng S thì sắp xếp B giảm dần

VD: (1, 8) (1, 6) (1, 4) (1, 3) (2, 5), (2, 5) (2, 4) (3, 7) (3, 6)

- Lúc này việc tìm "dãy con tăng" (theo cả S và B) dài nhất sẽ quy về việc tìm dãy con tăng dài nhất theo B:
+ Các phần tử có cùng S không bị ghép với nhau
+ VD (1, 8) không thể bị ghép vào sau (1, 3) vì (1, 3) chưa xuất hiện
+ Các phần tử có cùng S và cùng B không bị ghép với nhau
+ VD (2, 5) không thể bị ghép vào sau (2, 5) vì B phải tăng dần

# input ...
people = []
for i = 0 -> n - 1:
    people.append((S[i], -B[i], i))
people.sort()
#
dp = [1] * n # dp[i] = LIS | the last element is people[i]

for i = 1 -> n - 1:
    for j = 0 -> i - 1:
        if(B[j] < B[i]):
            dp[i] = max(dp[i], dp[j] + 1)
            
print(max(dp[]))

**Cải tiến với Binary search**

# input ...
people = []
for i = 0 -> n - 1:
    people.append((S[i], -B[i], i + 1))
people.sort()
#
dp = [] # dp[i] = index of the smallest possible last element of an increasing subsequence of length i + 1

int findPosition(int i):
    l = 0; r = len(dp) - 1; pos = len(dp)
    # find the first position in dp whose >= people[i].B
    while(l <= r):
        mid = (l + r) / 2
        # B is negative so we need to reverse it before compare
        if(-people[dp[mid]][1] >= -people[i][1]):
            pos = mid
            r = mid - 1
        else:
            l = mid + 1
    
    return pos

# dp LIS
for i = 0 -> n - 1:
    pos = findPosition(i)
    if(pos >= len(dp)):
        dp.append(i)
    else:
        dp[pos] = i
            
print(len(dp))

**Truy vết**

# input ...
people = []
for i = 0 -> n - 1:
    people.append((S[i], -B[i], i + 1))
people.sort()
#
dp = [] # dp[i] = index of the smallest possible last element of an increasing subsequence of length i + 1
previous = [-1] * n

int findPosition(int i):
    l = 0; r = len(dp) - 1; pos = len(dp)
    # find the first position in dp whose >= people[i].B
    while(l <= r):
        mid = (l + r) / 2
        # B is negative so we need to reverse it before compare
        if(-people[dp[mid]][1] >= -people[i][1]):
            pos = mid
            r = mid - 1
        else:
            l = mid + 1
    
    return pos

# dp LIS
for i = 0 -> n - 1:
    pos = findPosition(i)
    if(pos >= len(dp)):
        dp.append(i)
    else:
        dp[pos] = i
    
    previous[i] = pos <= 0 ? -1 : dp[pos - 1]
            
# print result
result = len(dp)
invitedPeople = []
cur = dp[-1]

while(cur >= 0):
    invitedPeople.append(people[cur].index)
    cur = previous[cur]
    
reverse(invitedPeople)

for p in invitedPeople:
    print(p,' ')

[Code C++](https://ideone.com/Gv0JN0)

**Độ phức tạp:** $O(NlogN)$