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