| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1088151 |
2024-09-14T03:40:08 Z |
Oz121 |
Sateliti (COCI20_satellti) |
Java 11 |
|
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()); }
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
