cjsladk   2년 전

채점 데이터가 빈약합니다. 해당 코드 알고리즘은 n^2 임에도 PyPy3에서 통과가 됩니다.

kep1er07   2년 전

최대 케이스가 들어 있음을 assert문으로 확인했습니다. PyPy3이 빠른데다 추가 시간까지 겹쳐 N, M <= 100,000이 뚫리는 것은 막을 수 없을 것 같습니다.

jiminp   2년 전

최대 케이스가 들어있지 않습니다.

아래와 같은 코드(+문제 해결을 위한 최소한의 수정)가 통과되고 있습니다.

N = M = 최댓값이고, A가 모두 서로 다르고, B의 모든 값이 A의 최댓값인 입력의 경우 아래 코드의 expected_time은 10^10이 되어야 합니다.

N = M = 최댓값이고, B가 A의 permutation인 경우, expected_time은 대략 5 * 10^9가 되어야 합니다.

즉, 다음과 같은 데이터들이 추가되어야 할 것으로 보입니다. (모두 N, M = 10^5이며, A는 랜덤하게 생성되었으며 든 수가 다름)

  • B의 모든 수는 A의 최솟값
  • B의 모든 수는 A의 최댓값
  • B의 모든 수는 (고정된) A의 임의의 한 원소 (x 대강 세 벌)
  • B는 A의 정렬된 버전, 또는 정렬된 버전의 역순
  • B는 A를 임의로 섞은 것 (x 대강 세 벌)

kep1er07   2년 전

죄송합니다.

jiminp   2년 전

죄송할 것 까지는 없습니다. N = M = 최대치인 데이터가 있는 건 사실이니까요...

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