oj.uz

답안 #1088158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088158 2024-09-14T03:46:42 Z Oz121 Sateliti (COCI20_satellti) Java 11
50 / 110
 3000 ms 162944 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 = 23; 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;

                    long l1 = (((vertSum[x+mid][y]-((x!=0) ? vertSum[x-1][y] : 0))%M)*inverse(pow(r,x)))%M; l1 = (l1+M)%M;
                    long l2 = (((vertSum[i+mid][j]-((i!=0) ? vertSum[i-1][j] : 0))%M)*inverse(pow(r,i)))%M; l2 = (l2+M)%M;

                    if (l1==l2) {
                        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 122 ms 11700 KB Output is correct
2 Correct 115 ms 12108 KB Output is correct
3 Correct 113 ms 11652 KB Output is correct
4 Correct 91 ms 10168 KB Output is correct
5 Correct 115 ms 11084 KB Output is correct
6 Correct 115 ms 10780 KB Output is correct
7 Correct 100 ms 10064 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 11700 KB Output is correct
2 Correct 115 ms 12108 KB Output is correct
3 Correct 113 ms 11652 KB Output is correct
4 Correct 91 ms 10168 KB Output is correct
5 Correct 115 ms 11084 KB Output is correct
6 Correct 115 ms 10780 KB Output is correct
7 Correct 100 ms 10064 KB Output is correct
8 Correct 1807 ms 29824 KB Output is correct
9 Correct 179 ms 15096 KB Output is correct
10 Correct 58 ms 8608 KB Output is correct
11 Correct 1789 ms 29628 KB Output is correct
12 Correct 1704 ms 29604 KB Output is correct
13 Correct 1849 ms 29608 KB Output is correct
14 Correct 1768 ms 29640 KB Output is correct
15 Correct 1831 ms 29532 KB Output is correct
16 Correct 1791 ms 29384 KB Output is correct
17 Correct 1752 ms 29648 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 11700 KB Output is correct
2 Correct 115 ms 12108 KB Output is correct
3 Correct 113 ms 11652 KB Output is correct
4 Correct 91 ms 10168 KB Output is correct
5 Correct 115 ms 11084 KB Output is correct
6 Correct 115 ms 10780 KB Output is correct
7 Correct 100 ms 10064 KB Output is correct
8 Correct 1807 ms 29824 KB Output is correct
9 Correct 179 ms 15096 KB Output is correct
10 Correct 58 ms 8608 KB Output is correct
11 Correct 1789 ms 29628 KB Output is correct
12 Correct 1704 ms 29604 KB Output is correct
13 Correct 1849 ms 29608 KB Output is correct
14 Correct 1768 ms 29640 KB Output is correct
15 Correct 1831 ms 29532 KB Output is correct
16 Correct 1791 ms 29384 KB Output is correct
17 Correct 1752 ms 29648 KB Output is correct
18 Execution timed out 3052 ms 162944 KB Time limit exceeded
19 Halted 0 ms 0 KB -