Submission #1088141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088141		Oz121	Sateliti (COCI20_satellti)	Java	10 / 110	1764 ms	29004 KiB

Main

import java.io.*;
import java.util.*;
public class Main { //Solution is modeled off the Tim Anishchuk's user solution on USACO guide.
    public static long p = 2; public static int q = 3; public static long r = 7; public static long M = (long) (1e9)+9;
    public static int num; public static int m;
    public static long[][] hash; public static long[][] prefix;
    public static void main(String[] args) throws IOException {
        FastIO io = new FastIO(); num = io.nextInt(); m = io.nextInt();
        int[][] arr = new int[num*2][m*2]; //Create four neighboring copies which makes processing column/row shifts as just a sub-matrix query

        for (int i = 0;i<num;i++) {
            String s = io.next();
            for (int j = 0;j<m;j++) {
                int add = (s.charAt(j)=='*') ? 31 : 17;
                arr[i][j] = add; arr[i+num][j] = add; arr[i][j+m] = add; arr[i+num][j+m] = add;
            }
        }
        hash = hash(arr); prefix = new long[num*2][m*2]; prefix[0][0] = hash[0][0];
        for (int i = 1;i<num*2;i++) prefix[i][0] = prefix[i-1][0]+hash[i][0];
        for (int j = 1;j<m*2;j++) prefix[0][j] = prefix[0][j-1]+hash[0][j];

        for (int i = 1;i<num*2;i++) {
            for (int j = 1;j<m*2;j++) {
                prefix[i][j] = (prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+hash[i][j])%M;
            }
        }

        /*for (int i = 0;i<num*2;i++) {
            for (int j = 0;j<m*2;j++) {
                io.print(prefix[i][j]+" ");
            }
            io.println();
        }*/
        long[][] rowHash = new long[num*2][m];
        for (int i = 0;i<num*2;i++) {
            for (int j = 0;j<m;j++) rowHash[i][j] = getHash(i,j,i,j+m-1);
        }

        long[][] vertSum = new long[num*2][m]; //Vertical prefix sums of the rowHash
        for (int j = 0;j<m;j++) vertSum[0][j] = rowHash[0][j];
        for (int i = 1;i<num*2;i++) {
            for (int j = 0;j<m;j++) vertSum[i][j] = (vertSum[i-1][j]+rowHash[i][j]*pow(r,i))%M;
        }

        int x = 0; int y = 0; //The answer sub-matrix
        for (int i = 0;i<num;i++) {
            for (int j = 0;j<m;j++) {
                int l = 0; int h = num-1; //Find the first different row

                while (l<h) {
                    int mid = (l+h)/2;

                    if ((vertSum[x+mid][y]-((x!=0) ? vertSum[x-1][y] : 0))*inverse(pow(r,x))
                            ==(vertSum[i+mid][j]-((i!=0) ? vertSum[i-1][j] : 0))*inverse(pow(r,j))) {
                        l = mid+1;
                    } else {
                        h = mid;
                    }
                }
                int r = l;

                l = 0; h = m-1; //Find the first different column within row r.
                while (l<h) {
                    int mid = (l+h)/2;

                    if (getHash(x+r,y,x+r,y+mid)==getHash(i+r,j,i+r,j+mid)) {
                        l = mid+1;
                    } else {
                        h = mid;
                    }
                }
                int c = l;
                if (arr[i+r][j+c]>arr[x+r][y+c]) {x = i; y = j;}
            }
        }

        for (int i = x;i<x+num;i++) {
            for (int j = y;j<y+m;j++) {
                if (arr[i][j]==31) io.print("*");
                else io.print(".");
            }
            io.println();
        }
        io.close();
    }

    public static long getHash (int i1, int j1, int i2, int j2) {
        long sum = prefix[i2][j2];
        sum -= (i1==0) ? 0 : prefix[i1-1][j2];
        sum -= (j1==0) ? 0 : prefix[i2][j1-1];
        sum += (i1==0||j1==0) ? 0 : prefix[i1-1][j1-1];
        sum = sum%M; sum = (sum+M)%M;

        long inv = (inverse(pow(p,i1))*inverse(pow(q,j1)))%M;
        return (sum*inv)%M;
    }

    public static long[][] hash (int[][] arr) {
        long[][] hash = new long[num*2][m*2];
        for (int i = 0;i<num*2;i++) {
            for (int j = 0;j<m*2;j++) {
                long pow = (pow(p,i)*pow(q,j))%M;
                hash[i][j] = (arr[i][j]*pow)%M;
            }
        }
        return hash;
    }

    public static long inverse (long a) { //Returns a/b modulo mod
        return pow(a,M-2);
    }
    public static long pow (long a, long b) {
        if (b==0) return 1;

        long temp = pow(a,b/2); temp = (temp*temp)%M;
        if (b%2==0)
            return temp;
        else
            return (temp*a)%M;
    }
    public static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

        // standard input
        public FastIO() { this(System.in, System.out); }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) { throw new InputMismatchException(); }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) { throw new InputMismatchException(); }
                if (numChars == -1) {
                    return -1;  // end of file
                }
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do { c = nextByte(); } while (c <= ' ');

            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public int nextInt() {  // nextLong() would be implemented similarly
            int c;
            do { c = nextByte(); } while (c <= ' ');

            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9') { throw new InputMismatchException(); }
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public double nextDouble() { return Double.parseDouble(next()); }
    }
}

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