codefores 1118C

2019-02-21

1118C Palindromic Matrix. 며칠전에 있었던 Codeforces Round #540 (Div.3)의 문제다. 대회 당시에는 문제 자체를 잘 못 읽어서 조건을 좀 더 빡빡하게 생각했었다. 여튼 문제를 제대로 읽고나서도 palindromic 인지, 아닌지는 판별이 쉬웠는데 palindromic 하게 그리는 방법을 몰라서 제출을 못했었다.

Editorial을 결국 참고했는데, 이전에 내가 짰던 것보다 훨씬 간결했다. 풀이를 보고 나서 풀이가 어려웠던 게 아니라 좀 다른 데서 헤맸다. python으로 줄곧 풀다가, 좀 지나서 c++로 좀 풀다가, java로 푸는 건 얼마 되지 않아서 c++의 pair와 동등한 자료구조가 있는가?에서 헤맸다. 여태 java에는 튜플형 자료구조가 없는 걸로 알고 있었고, Pair 비슷한 클래스를 만들어서 제출한 코드들을 꽤 보기도 했다.

누가 한 말대로 ‘javafx가 망한거랑 java8에서 javafx를 쓰는것은 별개의 문제’이므로, 찝찝하지만 javafx.util.Pair가 있어서 썼고 그걸로 통과를 하긴 했는데…

다른 사람들한테 물어도, 스택오버플로나 다른 블로그 글들을 봐도 pair 자료형이 필요하면 만들어서 쓰는게 답인 것 같다. java에서 pair(와 비슷하게) 사용하는 방법에 대해서 좀 더 찾아봐야겠다. 코포 제출한 사람들보면 자기가 쓰는 클래스들을 만들어서 뒤에 다 붙여 들고다니던데, 나도 내가 쓸 것들을 만들어서 들고다녀야겠다.

import javafx.util.Pair;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] a = new int[1005];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n * n; i++) {
            int x = Integer.parseInt(st.nextToken());
            a[x]++;
        }

        ArrayList<Pair<Integer, Pair<Integer, Integer>>> cells = new ArrayList<>();
        for(int i = 0; i < (n + 1) / 2; i++) {
            for(int j = 0; j < (n + 1) / 2; j++) {
                Pair<Integer, Integer> p = new Pair<>(i, j);

                if(i != n - i - 1 && j != n - j - 1)
                    cells.add(new Pair<>(4, p));
                else if((i != n - i - 1) ^ (j != n - j - 1))
                    cells.add(new Pair<>(2, p));
                else
                    cells.add(new Pair<>(1, p));
            }
        }

        int[] sizes = { 4, 2, 1 };
        int[][] grid = new int[n][n];
        for(int cur: sizes) {
            int lst = 1;

            for(Pair<Integer, Pair<Integer, Integer>> it: cells) {
                if(it.getKey() != cur) continue;
                int i = it.getValue().getKey();
                int j = it.getValue().getValue();

                while(lst < 1001 && a[lst] < cur)
                    lst++;

                if(lst == 1001) {
                    System.out.println("NO");
                    return;
                }

                grid[i][j] = grid[n - i - 1][j] = grid[i][n - j - 1] = grid[n - i - 1][n - j - 1] = lst;
                a[lst] -= cur;
            }
        }

        System.out.println("YES");
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                System.out.print(grid[i][j] + " ");
            System.out.println();
        }
    }
}