結果

問題 No.3334 I hate Image Convolution
コンテスト
ユーザー kencho
提出日時 2025-10-09 02:25:58
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 5,006 bytes
コンパイル時間 2,760 ms
コンパイル使用メモリ 82,948 KB
実行使用メモリ 90,544 KB
最終ジャッジ日時 2025-11-07 20:32:56
合計ジャッジ時間 41,870 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;
// GPT5 Thinking
public class Main {
    // ---- Multiset for long (TreeMap-based) ----
    static class MultiSet {
        TreeMap<Long, Integer> mp = new TreeMap<>();
        void add(long x){ mp.put(x, mp.getOrDefault(x, 0)+1); }
        void addAll(long[] arr){ for(long x: arr) add(x); }
        boolean removeOne(long x){
            Integer c = mp.get(x);
            if(c==null) return false;
            if(c==1) mp.remove(x);
            else mp.put(x, c-1);
            return true;
        }
        Long pollFirst(){
            var e = mp.firstEntry();
            if(e==null) return null;
            long k = e.getKey();
            removeOne(k);
            return k;
        }
        Long ceiling(long need){
            var e = mp.ceilingEntry(need);
            return e==null ? null : e.getKey();
        }
        boolean isEmpty(){ return mp.isEmpty(); }
        int size(){
            int s=0;
            for(int c: mp.values()) s+=c;
            return s;
        }
        @Override public String toString(){ return mp.toString(); }
    }

    // 復元：成功 → 行列、失敗 → null
    static long[][] reconstruct(int N, long[] C) {
        long[][] A = new long[N][N];
        if (N <= 1) {
            // 2x2 和が無いので全 0 で OK。C も空である必要。
            return (C.length==0) ? A : null;
        }
        if (C.length != (N-1)*(N-1)) return null;

        // C の多重集合
        MultiSet ms = new MultiSet();
        for (long x : C) {
            if (x < 0) return null; // 非負以外は即不可能
            ms.add(x);
        }

        // 上端・左端を 0 で開始（境界の自由度）
        // (0,0) の 2x2 和に最小値を当てる
        Long s00 = ms.pollFirst();
        if (s00 == null) return null;
        // A[1][1] = s00 - (A00 + A10 + A01) = s00
        A[1][1] = s00;

        // 1 行目の残り（i=0, j=1..N-2）
        // needPrefix = A[0][j] + A[1][j] （ここで A[0][j] は既決）
        for (int j = 1; j <= N-2; j++) {
            Long s = ms.pollFirst();
            if (s == null) return null;
            long needPrefix = A[0][j] + A[1][j]; // A[0][j] は 0 起点から順に決まる

            // A[0][j+1] を自由に増やせるので、A[1][j+1] が非負になるよう最小に分割
            long a01 = Math.max(0L, s - needPrefix);
            A[0][j+1] = a01;

            long a11 = s - needPrefix - a01;
            if (a11 < 0) return null; // 論理的に起こらないが保険
            A[1][j+1] = a11;
        }

        // 2 行目以降を左→右、上→下に埋める
        for (int i = 1; i <= N-2; i++) {
            for (int j = 0; j <= N-2; j++) {
                long need = A[i][j] + A[i+1][j] + A[i][j+1];
                Long s = ms.ceiling(need);
                if (s == null) {
                    return null; // 満たせる 2x2 和が残っていない → 不可能
                }
                ms.removeOne(s);
                A[i+1][j+1] = s - need; // 非負
            }
        }

        // 使い切れていることを確認
        if (!ms.isEmpty()) return null;
        return A;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            int N = fs.nextInt();
            int K = Math.max(0, (N-1)*(N-1));
            long[] C = new long[K];
            for (int i = 0; i < K; i++) C[i] = fs.nextLong();

            long[][] A = reconstruct(N, C);
            if (A == null) {
                out.append("-1\n");
            } else {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (j>0) out.append(' ');
                        out.append(A[i][j]);
                    }
                    out.append('\n');
                }
            }
        }
        System.out.print(out.toString());
    }

    // ---- Fast Scanner ----
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1<<16];
        private int ptr=0, len=0;
        FastScanner(InputStream is){ in=is; }
        private int read() throws IOException{
            if(ptr>=len){
                len=in.read(buffer); ptr=0;
                if(len<=0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException{
            StringBuilder sb=new StringBuilder();
            int c;
            while((c=read())!=-1 && c<=32);
            if(c==-1) return null;
            do{ sb.append((char)c); } while((c=read())!=-1 && c>32);
            return sb.toString();
        }
        int nextInt() throws IOException{ return Integer.parseInt(next()); }
        long nextLong() throws IOException{ return Long.parseLong(next()); }
    }
}
0