Submission #24,907

2026-02-16 17:45:55

pypy3

Accepted 75/75

90ms

22248 KiB

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = []
    for i in range(n):
        x, y = [int(x) for x in input().split()]
        if y < 4: continue
        if y == 4: a.append((x, False, i+1))
        else: a.append((x, True, i+1))
    n = len(a)
    a.sort(reverse = True)
    l, r = 0, n
    while l < r-1:
        mid = (l+r) // 2
        cnt0, cnt1 = 0, 0
        i = 0
        t = 1
        while i < n and a[i][0] >= mid:
            if a[i][1]: cnt1 += 1
            else: cnt0 += 1
            i += 1
        for j in range(mid, 0, -1):
            while i < n and a[i][0] >= j:
                if a[i][1]: cnt1 += 1
                else: cnt0 += 1
                i += 1
            if cnt0:
                cnt0 -= 1
                if cnt1: cnt1 -= 1
                else:
                    t = 0
                    break
            else:
                if cnt1 >= 2: cnt1 -= 2
                else:
                    t = 0
                    break
        if t: l = mid
        else: r = mid
    print(l)
    ans0, ans1 = [], []
    i0, i1 = 0, 0
    i = 0
    ans = []
    while i < n and a[i][0] >= l:
        if a[i][1]: ans1.append(a[i][2])
        else: ans0.append(a[i][2])
        i += 1
    for j in range(l, 0, -1):
        while i < n and a[i][0] >= j:
            if a[i][1]: ans1.append(a[i][2])
            else: ans0.append(a[i][2])
            i += 1
        if len(ans0) > i0:
            ans.append((ans0[i0], ans1[i1]))
            i0 += 1
            i1 += 1
        else:
            ans.append((ans1[i1], ans1[i1+1]))
            i1 += 2
    ans.reverse()
    for u in ans: print(*u)

solve()

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
subtask1	0/0	1	Accepted	45ms	19692 KiB
subtask2	10/10
		2	Accepted	39ms	19828 KiB
		3	Accepted	39ms	19672 KiB
		4	Accepted	45ms	19712 KiB
		5	Accepted	43ms	19780 KiB
		6	Accepted	46ms	19684 KiB
		7	Accepted	39ms	19660 KiB
		8	Accepted	39ms	19804 KiB
		9	Accepted	43ms	19692 KiB
		10	Accepted	39ms	19744 KiB
		11	Accepted	46ms	19688 KiB
subtask3	20/20
		12	Accepted	39ms	19872 KiB
		13	Accepted	39ms	19708 KiB
		14	Accepted	43ms	19816 KiB
		15	Accepted	43ms	19664 KiB
		16	Accepted	46ms	19688 KiB
		17	Accepted	46ms	21064 KiB
		18	Accepted	46ms	21224 KiB
		19	Accepted	48ms	21080 KiB
		20	Accepted	50ms	21304 KiB
		21	Accepted	56ms	21736 KiB
		22	Accepted	45ms	21212 KiB
		23	Accepted	71ms	22060 KiB
		24	Accepted	68ms	21996 KiB
		25	Accepted	59ms	21892 KiB
		26	Accepted	50ms	21060 KiB
		27	Accepted	76ms	21984 KiB
		28	Accepted	76ms	22108 KiB
		29	Accepted	45ms	21228 KiB
		30	Accepted	70ms	21992 KiB
		31	Accepted	76ms	22048 KiB
subtask4	15/15
		32	Accepted	46ms	19764 KiB
		33	Accepted	43ms	19796 KiB
		34	Accepted	39ms	19704 KiB
		35	Accepted	43ms	21020 KiB
		36	Accepted	54ms	21572 KiB
		37	Accepted	61ms	21476 KiB
		38	Accepted	50ms	21172 KiB
		39	Accepted	43ms	21212 KiB
		40	Accepted	48ms	21476 KiB
		41	Accepted	67ms	21784 KiB
		42	Accepted	56ms	21848 KiB
		43	Accepted	68ms	21976 KiB
		44	Accepted	43ms	21228 KiB
		45	Accepted	59ms	21476 KiB
		46	Accepted	68ms	22248 KiB
subtask5	15/15
		47	Accepted	45ms	21396 KiB
		48	Accepted	46ms	21376 KiB
		49	Accepted	50ms	21220 KiB
		50	Accepted	48ms	21188 KiB
		51	Accepted	52ms	21044 KiB
		52	Accepted	43ms	21228 KiB
		53	Accepted	48ms	21264 KiB
		54	Accepted	46ms	21220 KiB
		55	Accepted	39ms	19948 KiB
		56	Accepted	52ms	21536 KiB
		57	Accepted	48ms	21112 KiB
		58	Accepted	48ms	21112 KiB
		59	Accepted	54ms	21136 KiB
		60	Accepted	48ms	21032 KiB
		61	Accepted	41ms	21224 KiB
subtask6	15/15
		62	Accepted	50ms	21436 KiB
		63	Accepted	52ms	21452 KiB
		64	Accepted	71ms	21704 KiB
		65	Accepted	90ms	22212 KiB
		66	Accepted	79ms	22092 KiB
		67	Accepted	43ms	21188 KiB
		68	Accepted	59ms	21480 KiB
		69	Accepted	54ms	21168 KiB
		70	Accepted	48ms	21480 KiB
		71	Accepted	82ms	22104 KiB
		72	Accepted	56ms	21476 KiB
		73	Accepted	65ms	22064 KiB
		74	Accepted	67ms	21924 KiB
		75	Accepted	61ms	21480 KiB
		76	Accepted	43ms	21152 KiB