DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

Four Integer

문제로 돌아가기

해설

모든 Ai+BjA_i+B_jAi​+Bj​를 배열 XXX에, 모든 Ck+DℓC_k+D_\ellCk​+Dℓ​을 배열 YYY에 넣는다. 두 배열의 길이는 각각 n2n^2n2이다. 같은 합을 만드는 인덱스 쌍도 각각 넣어야 한다.

두 배열을 오름차순으로 정렬한다. XXX에서는 아직 처리하지 않은 최솟값 xxx를, YYY에서는 아직 처리하지 않은 최댓값 yyy를 본다. x+y<0x+y<0x+y<0이면 남은 어떤 의 원소를 에 더해도 이 되지 않으므로 쪽을 전진시킨다. 이면 남은 어떤 의 원소를 에 더해도 이 되지 않으므로 쪽을 전진시킨다.

x+y=0x+y=0x+y=0이면 xxx와 yyy가 연속해서 나오는 횟수를 각각 p,qp,qp,q라 하자. 두 묶음에서 하나씩 고르는 pqpq가지가 모두 정답에 포함된다. 이 값을 더하고 양쪽에서 해당 묶음을 건너뛴다. 각 값과 합이 이 되는 상대 값은 하나뿐이므로, 이 과정에서 같은 인덱스 튜플을 두 번 세지 않는다.

시간 복잡도는 O(n2log⁡n)O(n^2\log n)O(n2logn)이고 공간 복잡도는 O(n2)O(n^2)O(n2)이다. 네 원소의 합은 32비트 부호 있는 정수 범위에 들어가지만, 개수의 곱과 정답은 최대 4 0004=256 000 000이므로 64비트 정수로 계산한다.

Solution written by GPT

YYY
xxx
000
XXX
x+y>0x+y>0x+y>0
XXX
yyy
000
YYY
pq
000
 000 0004\,000^4=256\,000\,000\,000\,000
40004=256000000000000