Submission #1211938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211938		uranium235	Sateliti (COCI20_satellti)	Java	110 / 110	948 ms	54416 KiB

Main

// package ojuz;

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class Main {
    public static final long mod = (1L << 61) - 1, b = ThreadLocalRandom.current().nextLong(mod);
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]);
        String[] grid = new String[n];
        for (int i = 0; i < n; i++) grid[i] = reader.readLine();
        Hash hash = new Hash(grid);

        int[] best = new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cmp = hash.compare(best[0], best[1], i, j);
                if (cmp > 0) {
                    best[0] = i;
                    best[1] = j;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                writer.write(grid[(i + best[0]) % n].charAt((j + best[1]) % m));
            }
            writer.newLine();
        }
        writer.flush();
    }

    static class Hash {
        public final long[][] grid;
        public final long[] inv;
        public final String[] str;
        public final int n, m;
        public Hash(String[] strs) {
            this.n = strs.length;
            this.m = strs[0].length();

            this.str = strs;

            // inv[i] = mod inverse of (b ** i)
            this.inv = new long[n * m];
            this.inv[n * m - 1] = pow(b, mod - n * m);
            for (int i = n * m - 2; i >= 0; i--) inv[i] = mult(inv[i + 1], b);
            this.grid = new long[2 * n][2 * m];

            long current = 1;
            for (int i = 1; i < 2 * n; i++) {
                for (int j = 1; j < 2 * m; j++) {
//                    grid[i][j] = m * (i - 1L) + j - 1;
//                    grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
                    grid[i][j] = ((grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]) + mult(current, strs[(i - 1) % n].charAt((j - 1) % m))) % mod;
                    grid[i][j] = (grid[i][j] + mod) % mod;
                    current = mult(current, b);
                }
                current = mult(current, inv[m - 1]);
            }
        }


        public long get(int r, int c, int l) {
            int full = l / m;
            long result = (grid[r + full][c + m] - grid[r][c + m] - grid[r + full][c] + grid[r][c]) % mod;
            result = (result + mod) % mod;
            int remain = l % m;
            if (remain != 0) {
                result += (grid[r + full + 1][c + remain] - grid[r + full][c + remain] - grid[r + full + 1][c] + grid[r + full][c]) % mod;
                result = (result + mod) % mod;
            }
            return mult(result, inv[r * m + c]);
        }

        public int compare(int r1, int c1, int r2, int c2) {
            int lo = 0, hi = n * m;
            while (lo < hi) {
                int mid = lo + (hi - lo + 1) / 2;
                if (get(r1, c1, mid) == get(r2, c2, mid)) lo = mid;
                else hi = mid - 1;
            }
            if (lo == n * m) return 0;
            r1 += lo / m;
            r2 += lo / m;
            c1 += lo % m;
            c2 += lo % m;
            r1 %= n;
            r2 %= n;
            c1 %= m;
            c2 %= m;
            int cmp = Character.compare(str[r1].charAt(c1), str[r2].charAt(c2));
            if (cmp == 0) throw new RuntimeException();
            return cmp;
        }
    }

    public static long mult(long a, long b) {
        long low = a * b;
        return ((low & mod) + ((low >>> 61) | (Math.multiplyHigh(a, b) << 3))) % mod;
    }

    public static long pow(long a, long b) {
        long result = 1;
        while (b > 0) {
            if (b % 2 == 1) result = mult(result, a);
            a = mult(a, a);
            b /= 2;
        }
        return result;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60