oj.uz

Submission #995623

# Submission time Handle Problem Language Result Execution time Memory
995623 2024-06-09T13:34:11 Z doducanh Sateliti (COCI20_satellti) C++14
110 / 110
 504 ms 66388 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=1e3;
string s[maxn+7];
int h[maxn*2+7][maxn*2+7];
int pq_pow[2*maxn+7][2*maxn+7];
int n,m;
int add(int a,int b){return (a+b)%mod;}
int sub(int a,int b){return add(a,mod-b);}
int mul(int a,int b){return 1ll*a*b%mod;}
void precalc()
{
    for(int i=1;i<=2*maxn;i++){
        for(int j=1;j<=2*maxn;j++){
            if(i==1&&j==1)pq_pow[i][j]=1;
            else if(i==1)pq_pow[i][j]=mul(pq_pow[i][j-1],2);
            else pq_pow[i][j]=mul(pq_pow[i-1][j],3);
        }
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*m;j++){
            int x=i,y=j;
            if(x>n)x=x-n;
            if(y>m)y=y-m;
            int val=mul(s[x][y]=='.',pq_pow[i][j]);
            h[i][j]=sub(add(add(h[i][j-1],h[i-1][j]),val),h[i-1][j-1]);
        }
    }
}
int get_h(int xo,int yo,int xt,int yt)
{
    return sub(add(h[xt][yt],h[xo-1][yo-1]),add(h[xo-1][yt],h[xt][yo-1]));
}
bool is_equal(int x1,int y1,int x2,int y2,int dx,int dy)
{
    int val1=mul(get_h(x1,y1,x1+dx-1,y1+dy-1),pq_pow[x2][y2]);
    int val2=mul(get_h(x2,y2,x2+dx-1,y2+dy-1),pq_pow[x1][y1]);
    return val1==val2;
}
main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    precalc();
    int solx=1,soly=1;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            int lo_dx=1,hi_dx=n;
            int res=-1;
            while(lo_dx<=hi_dx){
                int mid=(lo_dx+hi_dx)/2;
                if(!is_equal(solx,soly,x,y,mid,m)){
                    res=mid;
                    hi_dx=mid-1;
                }
                else lo_dx=mid+1;
            }
            if(res==-1)continue;
            int dx=res;
            int lo_dy=1,hi_dy=m;
            res=-1;
            while(lo_dy<=hi_dy){
                int mid=(lo_dy+hi_dy)/2;
                if(!is_equal(solx+dx-1,soly,x+dx-1,y,1,mid)){
                    res=mid;
                    hi_dy=mid-1;
                }
                else lo_dy=mid+1;
            }
            if(res==-1)continue;
            int dy=res;
            int i=x+dx-1,j=y+dy-1,u=solx+dx-1,v=soly+dy-1;
            if(i>n)i-=n;
            if(j>m)j-=m;
            if(u>n)u-=n;
            if(v>m)v-=m;
            if(s[i][j]<s[u][v]){
                solx=x;
                soly=y;
            }
        }
    }
//    cout<<get_h(1,2,1,4)<<"\n";
//    cout<<get_h(2,2,2,4)<<"\n";
//    cout<<solx<<" "<<soly<<"\n";
//    cout<<get_h(2,2,2+3-1,2+1-1)<<"\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int x=solx+i,y=soly+j;
            if(x>n)x=x-n;
            if(y>m)y=y-m;
            cout<<s[x][y];
        }
        cout<<"\n";
    }
    return 0;
}

Compilation message

Main.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 11 ms 33432 KB Output is correct
3 Correct 11 ms 33372 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 11 ms 33372 KB Output is correct
6 Correct 11 ms 33372 KB Output is correct
7 Correct 10 ms 33372 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 11 ms 33432 KB Output is correct
3 Correct 11 ms 33372 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 11 ms 33372 KB Output is correct
6 Correct 11 ms 33372 KB Output is correct
7 Correct 10 ms 33372 KB Output is correct
8 Correct 43 ms 38740 KB Output is correct
9 Correct 11 ms 33372 KB Output is correct
10 Correct 11 ms 35292 KB Output is correct
11 Correct 50 ms 38720 KB Output is correct
12 Correct 47 ms 38740 KB Output is correct
13 Correct 45 ms 38996 KB Output is correct
14 Correct 46 ms 38984 KB Output is correct
15 Correct 43 ms 38996 KB Output is correct
16 Correct 48 ms 38996 KB Output is correct
17 Correct 54 ms 38996 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 11 ms 33432 KB Output is correct
3 Correct 11 ms 33372 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 11 ms 33372 KB Output is correct
6 Correct 11 ms 33372 KB Output is correct
7 Correct 10 ms 33372 KB Output is correct
8 Correct 43 ms 38740 KB Output is correct
9 Correct 11 ms 33372 KB Output is correct
10 Correct 11 ms 35292 KB Output is correct
11 Correct 50 ms 38720 KB Output is correct
12 Correct 47 ms 38740 KB Output is correct
13 Correct 45 ms 38996 KB Output is correct
14 Correct 46 ms 38984 KB Output is correct
15 Correct 43 ms 38996 KB Output is correct
16 Correct 48 ms 38996 KB Output is correct
17 Correct 54 ms 38996 KB Output is correct
18 Correct 409 ms 66132 KB Output is correct
19 Correct 17 ms 41308 KB Output is correct
20 Correct 18 ms 33520 KB Output is correct
21 Correct 399 ms 66168 KB Output is correct
22 Correct 504 ms 66168 KB Output is correct
23 Correct 394 ms 66388 KB Output is correct
24 Correct 475 ms 66160 KB Output is correct
25 Correct 406 ms 66172 KB Output is correct
26 Correct 434 ms 66180 KB Output is correct
27 Correct 472 ms 66132 KB Output is correct