Dirty Deeds Done Dirt Cheap (Codeforces 1148D)
Tags: Greedy, sortings

You are given $$$n$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$. All of the integers in the pairs are distinct and are in the range from $$$1$$$ to $$$2 \cdot n$$$ inclusive.Let's call a sequence of integers $$$x_1, x_2, \ldots, x_{2k}$$$ good if either   $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$, or  $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$. You need to choose a subset of distinct indices $$$i_1, i_2, \ldots, i_t$$$ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$), this sequence is good.What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $$$i_1, i_2, \ldots, i_t$$$.

Input: The first line contains single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the number of pairs.Each of the next $$$n$$$ lines contain two numbers — $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — the elements of the pairs.It is guaranteed that all integers in the pairs are distinct, that is, every integer from $$$1$$$ to $$$2 \cdot n$$$ is mentioned exactly once.

Output: In the first line print a single integer $$$t$$$ — the number of pairs in the answer.Then print $$$t$$$ distinct integers $$$i_1, i_2, \ldots, i_t$$$ — the indexes of pairs in the corresponding order.

Note: The final sequence in the first example is $$$1 < 7 > 3 < 5 > 2 < 10$$$.The final sequence in the second example is $$$6 > 1 < 3 > 2 < 5 > 4$$$.

Sample Inputs:
5
1 7
6 4
2 10
9 8
3 5

3
5 4
3 2
6 1

Sample Outputs:
3
1 5 3

3
3 2 1

Solution (Python):
import math
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations, count, product
inf = math.inf

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def quick_pow(x, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % mod
        x = x * x % mod
        n >>= 1
    return res

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True

class BIT:

    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

def main():
    n = II()
    (a, b) = ([], [])
    cnt = 0
    for _ in range(n):
        (x, y) = MII()
        a.append(x)
        b.append(y)
        if x > y:
            cnt += 1
    if cnt * 2 >= n:
        chosen = [i for i in range(n) if a[i] > b[i]]
        chosen.sort(key=lambda x: a[x])
    else:
        chosen = [i for i in range(n) if a[i] < b[i]]
        chosen.sort(key=lambda x: -b[x])
    print(len(chosen))
    print(' '.join((str(x + 1) for x in chosen)))
    return
t = 1
for _ in range(t):
    main()

Solution (Python):
import atexit
import io
import sys
_I_B = sys.stdin.read().splitlines()
input = iter(_I_B).__next__
_O_B = io.StringIO()
sys.stdout = _O_B

@atexit.register
def write():
    sys.__stdout__.write(_O_B.getvalue())

def main():
    n = int(input())
    g = [[], []]
    for _ in range(n):
        (x, y) = map(int, input().split())
        g[y > x].append((x, y, _ + 1))

    def secondAsc(elem):
        return elem[1]

    def secondDsc(elem):
        return -elem[1]
    if len(g[0]) >= n / 2:
        g[0].sort(key=secondAsc)
        print(len(g[0]))
        for (i, j, k) in g[0]:
            print(k, end=' ')
    else:
        g[1].sort(key=secondDsc)
        print(len(g[1]))
        for (i, j, k) in g[1]:
            print(k, end=' ')
    print()
if __name__ == '__main__':
    main()

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI():
    return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
    return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
    return [float(x) for x in sys.stdin.readline().split()]

def LS():
    return sys.stdin.readline().split()

def I():
    return int(sys.stdin.readline())

def F():
    return float(sys.stdin.readline())

def S():
    return input()

def pf(s):
    return print(s, flush=True)

def pe(s):
    return print(str(s), file=sys.stderr)

def main():
    n = I()
    aa = [LI() for _ in range(n)]
    a = []
    b = []
    for i in range(1, n + 1):
        (c, d) = aa[i - 1]
        if c < d:
            a.append((c, i))
        else:
            b.append((c, i))
    if len(a) >= len(b):
        a.sort(key=lambda x: -x[0])
        r = a
    else:
        b.sort(key=lambda x: x[0])
        r = b
    return '{}\n{}'.format(len(r), ' '.join(map(lambda x: str(x[1]), r)))
print(main())