oj.uz

답안 #1088155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088155 2024-09-14T03:43:07 Z Oz121 Sateliti (COCI20_satellti) Java 11
10 / 110
 1809 ms 29584 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 = 41; 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 115 ms 11852 KB Output is correct
2 Correct 114 ms 11648 KB Output is correct
3 Correct 117 ms 11856 KB Output is correct
4 Correct 105 ms 10676 KB Output is correct
5 Correct 108 ms 10980 KB Output is correct
6 Correct 108 ms 10756 KB Output is correct
7 Correct 99 ms 10852 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 11852 KB Output is correct
2 Correct 114 ms 11648 KB Output is correct
3 Correct 117 ms 11856 KB Output is correct
4 Correct 105 ms 10676 KB Output is correct
5 Correct 108 ms 10980 KB Output is correct
6 Correct 108 ms 10756 KB Output is correct
7 Correct 99 ms 10852 KB Output is correct
8 Correct 1761 ms 29364 KB Output is correct
9 Correct 156 ms 14428 KB Output is correct
10 Correct 50 ms 8928 KB Output is correct
11 Correct 1769 ms 29568 KB Output is correct
12 Correct 1680 ms 29584 KB Output is correct
13 Correct 1786 ms 29248 KB Output is correct
14 Correct 1699 ms 29276 KB Output is correct
15 Correct 1809 ms 28996 KB Output is correct
16 Correct 1791 ms 29324 KB Output is correct
17 Incorrect 1745 ms 29344 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 11852 KB Output is correct
2 Correct 114 ms 11648 KB Output is correct
3 Correct 117 ms 11856 KB Output is correct
4 Correct 105 ms 10676 KB Output is correct
5 Correct 108 ms 10980 KB Output is correct
6 Correct 108 ms 10756 KB Output is correct
7 Correct 99 ms 10852 KB Output is correct
8 Correct 1761 ms 29364 KB Output is correct
9 Correct 156 ms 14428 KB Output is correct
10 Correct 50 ms 8928 KB Output is correct
11 Correct 1769 ms 29568 KB Output is correct
12 Correct 1680 ms 29584 KB Output is correct
13 Correct 1786 ms 29248 KB Output is correct
14 Correct 1699 ms 29276 KB Output is correct
15 Correct 1809 ms 28996 KB Output is correct
16 Correct 1791 ms 29324 KB Output is correct
17 Incorrect 1745 ms 29344 KB Output isn't correct
18 Halted 0 ms 0 KB -