글 읽기 - [python]반례 부탁드립니다.

john_cowart 2일 전 0

나름 dict로 시간초과는 피했다고 생각했는데.. 틀렸습니다가 뜨네요.

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    first_to_second={}
    second_to_first={}
    for _ in range(n):
        first,second=map(int,input().split())
        first_to_second[first]=second
        second_to_first[second]=first
    if first_to_second[1]==1:
        print(1)
        continue
    else:
        ans=0
        cri_first=second_to_first[1]
        cri_second=first_to_second[1]
        if cri_second<cri_first:
            for i in range(2,cri_second):
                if second_to_first[i]<cri_first:
                    ans+=1
        else:
            for i in range(2,cri_first):
                if first_to_second[i]<cri_second:
                    ans+=1
        print(ans+2)
        

nflight11 2일 전 0

testcase.ac를 사용한 결과입니다.

# Input of Counterexample 1
1
5
3 3
4 1
1 5
5 4
2 2

# Wrong answer
4

# Correct answer
3

======

# Input of Counterexample 2
1
8
1 4
3 2
4 6
6 7
7 5
8 1
5 3
2 8


# Wrong answer
4

# Correct answer
3

======

# Input of Counterexample 3
1
9
8 5
5 3
6 1
9 2
7 6
2 4
3 7
1 8
4 9

# Wrong answer
5

# Correct answer
4

yycdevel 2일 전 0

이 댓글은 반례는 아니지만요 1~n까지의 정수에 1~n까지의 정수를 대응시키는 건 리스트가 더 빠르지 않을까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python]반례 부탁드립니다.

john_cowart 2일 전 0

nflight11 2일 전 0

yycdevel 2일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말