oj.uz

답안 #1088151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088151 2024-09-14T03:40:08 Z Oz121 Sateliti (COCI20_satellti) Java 11
10 / 110
 1821 ms 29376 KB 
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 = 29; public static int q = 37; public static long r = 19; 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)=='*') ? 99713 : 10007;
                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;
            }
        }

        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)))%M
                            ==((vertSum[i+mid][j]-((i!=0) ? vertSum[i-1][j] : 0))*inverse(pow(r,i)))%M) {
                        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]==99713) 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 11732 KB Output is correct
2 Correct 115 ms 11540 KB Output is correct
3 Correct 111 ms 11944 KB Output is correct
4 Correct 104 ms 10988 KB Output is correct
5 Correct 111 ms 11520 KB Output is correct
6 Correct 115 ms 10708 KB Output is correct
7 Correct 113 ms 10516 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 11732 KB Output is correct
2 Correct 115 ms 11540 KB Output is correct
3 Correct 111 ms 11944 KB Output is correct
4 Correct 104 ms 10988 KB Output is correct
5 Correct 111 ms 11520 KB Output is correct
6 Correct 115 ms 10708 KB Output is correct
7 Correct 113 ms 10516 KB Output is correct
8 Correct 1757 ms 29252 KB Output is correct
9 Correct 157 ms 14604 KB Output is correct
10 Correct 50 ms 9272 KB Output is correct
11 Correct 1745 ms 29212 KB Output is correct
12 Correct 1691 ms 29352 KB Output is correct
13 Correct 1797 ms 29080 KB Output is correct
14 Correct 1696 ms 29376 KB Output is correct
15 Correct 1821 ms 29296 KB Output is correct
16 Correct 1760 ms 29000 KB Output is correct
17 Incorrect 1704 ms 29228 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 11732 KB Output is correct
2 Correct 115 ms 11540 KB Output is correct
3 Correct 111 ms 11944 KB Output is correct
4 Correct 104 ms 10988 KB Output is correct
5 Correct 111 ms 11520 KB Output is correct
6 Correct 115 ms 10708 KB Output is correct
7 Correct 113 ms 10516 KB Output is correct
8 Correct 1757 ms 29252 KB Output is correct
9 Correct 157 ms 14604 KB Output is correct
10 Correct 50 ms 9272 KB Output is correct
11 Correct 1745 ms 29212 KB Output is correct
12 Correct 1691 ms 29352 KB Output is correct
13 Correct 1797 ms 29080 KB Output is correct
14 Correct 1696 ms 29376 KB Output is correct
15 Correct 1821 ms 29296 KB Output is correct
16 Correct 1760 ms 29000 KB Output is correct
17 Incorrect 1704 ms 29228 KB Output isn't correct
18 Halted 0 ms 0 KB -