Submission #829205

#	Time	Username	Problem	Language	Result	Execution time	Memory
829205		boyliguanhan	Sateliti (COCI20_satellti)	C++17	0 / 110	1 ms	980 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int hsh[2010][2010], pw[2010][2], mod = 1e9+7, n, m;
int calc_hash(int a, int b, int c, int d) {
    return hsh[c][d]-hsh[c][b-1]-hsh[a-1][d]+hsh[a-1][b-1];
}
bool check(int a, int b, int c, int d, int N, int M) {
    int hasha=calc_hash(a,b,a+N,b+M), hashb = calc_hash(c,d,c+N,d+M);
    if(a<c)
        hasha=hasha*pw[c-a][0]%mod;
    if(a>c)
        hashb=hashb*pw[a-c][0]%mod;
    if(b<d)
        hasha=hasha*pw[d-b][1]%mod;
    if(b>d)
        hashb=hashb*pw[b-d][1]%mod;
    return hasha==hashb;
}
char str[2010][2010];
signed main() {
    pw[0][0]=pw[0][1]=1;
    for(int i = 1; i < 2010; i++)
        pw[i][0]=pw[i-1][0]*2%mod, pw[i][1]=pw[i-1][1]*3%mod;
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            str[i][j]=str[i+n][j]=str[i][j+m]=str[i+n][j+m]=c;
            hsh[i][j] = hsh[i+n][j] = hsh[i][j+m] = hsh[i+n][j+m] = (c=='*')*pw[i][0]*pw[j][1]%mod;
        }
    }
    for(int i = 1; i <= 2*n; i++)
        for(int j = 1; j <= 2*m; j++)
            hsh[i][j]+=hsh[i-1][j]+hsh[i][j-1]-hsh[i-1][j-1];
    int a=1,b=1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int l = 0, r = n-1;
            while(l<r) {
                int mid = l+r>>1;
                if(check(a,b,i,j,mid,m-1))
                    l=mid+1;
                else
                    r = mid;    
            }
            int l2 = 0, r2 = m-1;
            while(l2<r2) {
                int mid = l2+r2>>1;
                if(check(a,b,i,j,l,mid))
                    l2 = mid+1;
                else
                    r2 = mid;
            }
            if(str[a+l][b+l2]=='.'&&str[i+l][j+l2]=='*')
                a=i,b=j;
        }
    }
    cerr << a << ' ' << b << '\n';
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cout << str[i+a][j+b] << (j-m+1?"":"\n");
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |                 int mid = l+r>>1;
      |                           ~^~
Main.cpp:52:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |                 int mid = l2+r2>>1;
      |                           ~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60