CSES - Putka Open 2025 – 1/5

Submission details
Task:	Järjestys
Sender:	Metabolix
Submission time:	2025-12-04 13:36:47 +0200
Language:	Python3 (PyPy3)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	10
#3	ACCEPTED	10
#4	ACCEPTED	40
#5	ACCEPTED	30

Test results
test	verdict	time	group
#1	ACCEPTED	0.05 s	1, 4, 5	details
#2	ACCEPTED	0.06 s	1, 4, 5	details
#3	ACCEPTED	0.06 s	1, 4, 5	details
#4	ACCEPTED	0.07 s	1, 4, 5	details
#5	ACCEPTED	0.07 s	1, 4, 5	details
#6	ACCEPTED	0.07 s	1, 2, 4, 5	details
#7	ACCEPTED	0.07 s	1, 3, 4, 5	details
#8	ACCEPTED	0.07 s	1, 4, 5	details
#9	ACCEPTED	0.16 s	2, 4, 5	details
#10	ACCEPTED	0.20 s	3, 4, 5	details
#11	ACCEPTED	0.17 s	4, 5	details
#12	ACCEPTED	0.18 s	4, 5	details
#13	ACCEPTED	0.18 s	4, 5	details
#14	ACCEPTED	0.18 s	4, 5	details
#15	ACCEPTED	0.30 s	2, 5	details
#16	ACCEPTED	0.39 s	3, 5	details
#17	ACCEPTED	0.31 s	5	details
#18	ACCEPTED	0.33 s	5	details
#19	ACCEPTED	0.33 s	5	details
#20	ACCEPTED	0.34 s	5	details
#21	ACCEPTED	0.39 s	5	details
#22	ACCEPTED	0.40 s	5	details

Code

#!/usr/bin/env python3

def kelpaa(p):
    a = 0
    for x in p:
        if x[0] < a:
            return False
        a = x[1]
    return True

def osa1(p):
    # len(p) <= 5
    def rekursio(p, a):
        for i in range(len(p)):
            if p[i][0] >= a:
                p2 = p[:i] + p[i+1:]
                r = rekursio(p2, p[i][1]) if p2 else []
                if r is not None:
                    return [p[i]] + r
    return rekursio(p, 0) if len(p) <= 5 else None

def osa23(p):
    # x <= y aina tai x >= y aina, jolloin nouseva järjestys on oikea ratkaisu.
    p = sorted(p)
    if kelpaa(p):
        return p

def osa4(p):
    erikoismerkki = (1999999999, 0)
    alut = sorted(p + [erikoismerkki])
    loput = sorted(alut, key = lambda x: x[1])
    n = len(alut)
    kaaret = dict()
    for i in range(n):
        if not kelpaa([loput[i], alut[i]]):
            return None
        kaaret[loput[i]] = alut[i]

    syklit = dict()
    nähty = set()
    for i in range(n):
        if alut[i] in nähty:
            continue
        nykyinen = alut[i]
        sykli = set()
        while nykyinen not in sykli:
            sykli.add(nykyinen)
            nähty.add(nykyinen)
            nykyinen = kaaret[nykyinen]
        syklit[alut[i]] = sykli

    def yhdista():
        for s1_key in list(syklit.keys()):
            s1 = syklit[s1_key]
            for s2 in syklit.values():
                if s1 is s2:
                    continue
                for a2 in s2:
                    for a1 in s1:
                        b1 = kaaret[a1]
                        b2 = kaaret[a2]
                        if kelpaa([a1, b2]) and kelpaa([a2, b1]):
                            kaaret[a1] = b2
                            kaaret[a2] = b1
                            s2.update(s1)
                            del syklit[s1_key]
                            return True
        return False

    while yhdista():
        pass

    if len(syklit) > 1:
        return None
    ratkaisu = []
    a = erikoismerkki
    while kaaret[a] != erikoismerkki:
        a = kaaret[a]
        ratkaisu.append(a)
    if not kelpaa(ratkaisu):
        print(ratkaisu)
        raise Exception("Järjestys ei kelpaa vaikka pitäisi")
    return ratkaisu

t = int(input())
for _ in range(t):
    n = int(input())
    parit = []
    for i in range(n):
        a, b = map(int, input().split())
        parit.append((a, b, i))

    tulos = osa4(parit) #osa23(parit) or osa1(parit)
    if tulos is None:
        print("NO")
    else:
        print("YES")
        for p in tulos:
            print(p[0], p[1])

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 1 74 75 1 100 43 ...` view save

correct output
`YES 74 75 YES 100 43 YES ...` view save

user output
`YES 74 75 YES 100 43 YES ...` Truncated

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 2 80 54 51 61 2 ...` view save

correct output
`YES 51 61 80 54 YES 2 64 ...` view save

user output
`YES 51 61 80 54 YES 2 64 ...` Truncated

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 3 3 74 91 45 100 24 ...` view save

correct output
`YES 3 74 100 24 91 45 YES ...` view save

user output
`YES 3 74 100 24 91 45 YES ...` Truncated

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 4 88 50 62 41 12 86 ...` view save

correct output
`YES 12 86 88 50 62 41 66 93 ...` view save

user output
`YES 12 86 88 50 62 41 66 93 ...` Truncated

Test 5

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 82 80 80 92 5 22 ...` view save

correct output
`YES 5 22 94 13 82 80 80 92 ...` view save

user output
`YES 5 22 82 80 93 91 94 13 ...` Truncated

Test 6

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
`100 5 34 38 26 30 1 6 ...` view save

correct output
`YES 1 6 12 22 26 30 34 38 ...` view save

user output
`YES 1 6 12 22 26 30 34 38 ...` Truncated

Test 7

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
`100 5 50 40 28 25 51 7 ...` view save

correct output
`YES 51 7 50 40 47 1 17 11 ...` view save

user output
`YES 17 11 51 7 47 1 28 25 ...` Truncated

Test 8

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 2 2 2 1 1 1 ...` view save

correct output
`YES 1 2 2 1 2 1 1 1 ...` view save

user output
`YES 1 1 2 1 2 1 1 2 ...` Truncated

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

input
`100 100 175870020 296379324 248160539 883842002 21934885 781732852 ...` view save

correct output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` view save

user output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` Truncated

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

input
`100 100 447597377 314433951 700232436 691277009 937268439 708165426 ...` view save

correct output
`YES 998963839 391778929 995772196 257222033 995754704 553123757 994629465 247775824 ...` view save

user output
`YES 78989197 22224979 400940916 299338123 712093668 563049590 879335363 246462890 ...` Truncated

Test 11

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 1 1 1 2 2 1 ...` view save

correct output
`YES 1 2 2 1 1 2 2 2 ...` view save

user output
`YES 1 1 1 1 1 1 1 1 ...` Truncated

Test 12

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 7 1 6 3 10 9 ...` view save

correct output
`YES 6 7 7 8 9 10 10 10 ...` view save

user output
`YES 1 9 10 4 8 1 3 9 ...` Truncated

Test 13

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 51 5 85 77 91 84 ...` view save

correct output
`YES 100 24 100 25 100 3 100 6 ...` view save

user output
`YES 14 71 89 38 72 48 84 99 ...` Truncated

Test 14

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 823828194 863717310 593641073 340054211 420481158 965069109 ...` view save

correct output
`YES 999289319 634855378 996775156 433726648 983657502 55234695 981890636 112877413 ...` view save

user output
`YES 96663815 577521349 746260852 796491406 951642354 231712729 657249032 737709307 ...` Truncated

Test 15

Group: 2, 5

Verdict: ACCEPTED

input
`100 500 88724450 89315226 266915464 267648621 189301651 189661541 ...` view save

correct output
`YES 764920 1459946 1936195 2832987 3691481 4085931 4991808 5840928 ...` view save

user output
`YES 764920 1459946 1936195 2832987 3691481 4085931 4991808 5840928 ...` Truncated

Test 16

Group: 3, 5

Verdict: ACCEPTED

input
`100 500 763682761 317584504 756010800 260162861 435911339 78070399 ...` view save

correct output
`YES 998768285 3307355 998714926 628486754 997115613 820932481 993320616 554600893 ...` view save

user output
`YES 67893124 41695427 274367861 67563731 332912584 34815628 229876687 12838751 ...` Truncated

Test 17

Group: 5

Verdict: ACCEPTED

input
`100 500 2 2 2 1 1 2 ...` view save

correct output
`YES 1 2 2 2 2 1 1 2 ...` view save

user output
`YES 1 1 1 1 1 1 1 1 ...` Truncated

Test 18

Group: 5

Verdict: ACCEPTED

input
`100 500 10 6 10 10 9 10 ...` view save

correct output
`YES 2 3 3 4 4 5 5 6 ...` view save

user output
`YES 1 1 1 1 1 5 8 4 ...` Truncated

Test 19

Group: 5

Verdict: ACCEPTED

input
`100 500 85 87 89 70 70 92 ...` view save

correct output
`YES 96 97 100 67 100 10 100 97 ...` view save

user output
`YES 2 27 71 15 51 29 67 80 ...` Truncated

Test 20

Group: 5

Verdict: ACCEPTED

input
`100 500 861154169 119512584 569086662 606567153 288230434 322196278 ...` view save

correct output
`YES 999945324 969534372 999738857 240617694 999244114 722161553 999207839 557351400 ...` view save

user output
`YES 47896585 707808748 881709287 666121819 901309262 926146559 985986446 40084070 ...` Truncated

Test 21

Group: 5

Verdict: ACCEPTED

input
`100 500 116439250 401518028 280329609 193466222 674040956 209050570 ...` view save

correct output
`NO YES 773701149 773852119 987509190 315670966 977413249 510418200 ...` view save

user output
`NO YES 3227199 2158011 10589181 6964737 35547370 20725065 ...` Truncated

Test 22

Group: 5

Verdict: ACCEPTED

input
`100 500 934181189 942499518 684836806 395802802 957884803 570946201 ...` view save

correct output
`YES 999772640 505132174 999111650 140844643 999028633 888134186 999020109 291046771 ...` view save

user output
`YES 24314565 937625373 988195925 444535743 776311954 510244101 810194614 754386997 ...` Truncated

Putka Open 2025 – 1/5

Järjestys

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Tasks

Submissions (Metabolix)