홀수 행은 왼쪽에서 오른쪽, 짝수 행은 오른쪽에서 왼쪽으로 읽어 길이 의 뱀 모양 경로를 만든다. 이 경로에서 이웃한 두 칸은 실제 격자에서도 인접한다.
경로를 일차원 배열로 보고, 길이를 하나씩 줄이는 버블 정렬 비교를 모두 출력한다. 값은 읽을 필요가 없고, 각 비교·교환은 허용된 연산 하나로 구현된다. 오른쪽으로 이동하는 경로 간선은 종류 , 아래로 이동하는 간선은 종류 , 왼쪽으로 이동하는 간선은 종류 를 사용한다. 왼쪽 이동에서는 연산의 좌표를 왼쪽 칸으로 지정해야 한다.
첫 단계는 개의 연산으로 경로를 오름차순 정렬한다. 각 행에는 이미 그 행에 들어가야 하는 값들만 있지만, 짝수 행의 순서는 거꾸로 되어 있다. 모든 짝수 행을 종류 의 버블 정렬로 정렬한다.
총 연산 수는
출력 시간은 , 경로 저장 공간은 이다. 에서 이다. 이고, 채점 반복 횟수의 분자는 이다. 모든 계산은 64비트 정수 범위 안에 들어간다.
서브태스크 1의 단순 구현은 뱀 경로 전체를 번 반복해서 버블 정렬한다. 이후 짝수 행을 정렬하면 에서 각각 개 연산이므로 제한을 만족한다. 전체 범위에서는 이미 확정된 끝부분을 제외하여 첫 단계의 비교 수를 로 줄여야 한다.
체커는 연산을 공간에 저장한다. 시간에 검사한다.
Solution written by GPT6