oj.uz

답안 #1088163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088163 2024-09-14T03:48:38 Z Oz121 Sateliti (COCI20_satellti) Java 11
50 / 110
 3000 ms 163108 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 = 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)=='*') ? 17 : 11;
                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]==17) 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 119 ms 11312 KB Output is correct
2 Correct 114 ms 12264 KB Output is correct
3 Correct 114 ms 11788 KB Output is correct
4 Correct 102 ms 10160 KB Output is correct
5 Correct 110 ms 11364 KB Output is correct
6 Correct 113 ms 11468 KB Output is correct
7 Correct 100 ms 9820 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 11312 KB Output is correct
2 Correct 114 ms 12264 KB Output is correct
3 Correct 114 ms 11788 KB Output is correct
4 Correct 102 ms 10160 KB Output is correct
5 Correct 110 ms 11364 KB Output is correct
6 Correct 113 ms 11468 KB Output is correct
7 Correct 100 ms 9820 KB Output is correct
8 Correct 1779 ms 29608 KB Output is correct
9 Correct 168 ms 15156 KB Output is correct
10 Correct 57 ms 9288 KB Output is correct
11 Correct 1785 ms 29620 KB Output is correct
12 Correct 1705 ms 29668 KB Output is correct
13 Correct 1799 ms 29616 KB Output is correct
14 Correct 1740 ms 29580 KB Output is correct
15 Correct 1841 ms 29384 KB Output is correct
16 Correct 1806 ms 29544 KB Output is correct
17 Correct 1731 ms 29352 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 11312 KB Output is correct
2 Correct 114 ms 12264 KB Output is correct
3 Correct 114 ms 11788 KB Output is correct
4 Correct 102 ms 10160 KB Output is correct
5 Correct 110 ms 11364 KB Output is correct
6 Correct 113 ms 11468 KB Output is correct
7 Correct 100 ms 9820 KB Output is correct
8 Correct 1779 ms 29608 KB Output is correct
9 Correct 168 ms 15156 KB Output is correct
10 Correct 57 ms 9288 KB Output is correct
11 Correct 1785 ms 29620 KB Output is correct
12 Correct 1705 ms 29668 KB Output is correct
13 Correct 1799 ms 29616 KB Output is correct
14 Correct 1740 ms 29580 KB Output is correct
15 Correct 1841 ms 29384 KB Output is correct
16 Correct 1806 ms 29544 KB Output is correct
17 Correct 1731 ms 29352 KB Output is correct
18 Execution timed out 3104 ms 163108 KB Time limit exceeded
19 Halted 0 ms 0 KB -