Submission #685868

#	Time	Username	Problem	Language	Result	Execution time	Memory
685868		guagua0407	Sateliti (COCI20_satellti)	C++17	110 / 110	593 ms	37756 KiB

Main

/*
燒雞
 燒雞
  燒雞    好想進選訓
 燒雞
燒雞
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1005;
const int MOD=1e9+7;
char S[2*mxn][2*mxn];
ll hashv[2*mxn][2*mxn];
ll powx[2*mxn],powy[2*mxn];
random_device rng;
mt19937_64 seed(rng());
//ll X=abs((ll)seed());
//ll Y=abs((ll)seed());

ll X=3;
ll Y=4;

void genhash(int n,int m){
    powx[0]=powy[0]=1;
    for(int i=1;i<2*mxn;i++){
        powx[i]=(powx[i-1]*X)%MOD;
    }
    for(int i=1;i<2*mxn;i++){
        powy[i]=(powy[i-1]*Y)%MOD;
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*m;j++){
            hashv[i][j]=(hashv[i][j-1]*X%MOD+S[i][j])%MOD;
        }
    }
    for(int j=1;j<=2*m;j++){
        for(int i=1;i<=2*n;i++){
            hashv[i][j]=(hashv[i-1][j]*Y%MOD+hashv[i][j])%MOD;
        }
    }
}

int cal(int a,int b,int xx,int yy){
    int x=a+xx-1;
    int y=b+yy-1;
    ll ans=(hashv[x][y]-hashv[x][b-1]*powx[y-b+1]%MOD-hashv[a-1][y]*powy[x-a+1]%MOD);
    if(ans<0) ans+=MOD;
    ans=(ans+hashv[a-1][b-1]*powy[x-a+1]%MOD*powx[y-b+1])%MOD;
    return ans;
}

int main() {_
    //setIO("wayne");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>S[i][j];
            S[i+n][j]=S[i][j+m]=S[i+n][j+m]=S[i][j];
        }
    }
    genhash(n,m);
    int ansx=1,ansy=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int l=i-1,r=i+n-1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(cal(i,j,mid-i+1,m)==cal(ansx,ansy,mid-i+1,m)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            int row=l+1;
            l=j-1;
            r=j+m-1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(cal(row,j,1,mid-j+1)==cal(ansx+(row-i),ansy,1,mid-j+1)){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            int col=l+1;
            if(row<=i+n-1 and col<=j+m-1){
                if(S[row][col]<S[ansx+(row-i)][ansy+(col-j)]){
                    ansx=i,ansy=j;
                }
            }
        }
    }
    for(int i=ansx;i<=ansx+n-1;i++){
        for(int j=ansy;j<=ansy+m-1;j++){
            cout<<S[i][j];
        }
        cout<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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