Submission #557244

#	Time	Username	Problem	Language	Result	Execution time	Memory
557244		CyberSleeper	Sateliti (COCI20_satellti)	C++17	0 / 110	2 ms	1364 KiB

Main

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define i8          __int128
#define pi8         pair<i8, i8>
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define pii         pair<int, int>
#define ld          long double
#define arr3        array<ll, 3>
#define calc(x, y)  (sqr(X[x]-X[y])+sqr(Y[x]-Y[y]))
#define nl          '\n'
#define sqr(x)      (x)*(x)
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=1005, MOD=1000000007, KEY1=177013, KEY2=10007, BLOCK=400, INF=2e9+7;
const ll INFF=1000000000000000007;
const ld ERR=1e-6, pi=3.14159265358979323846;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll N, M, key1[2*MX], key2[2*MX], ansx=1, ansy=1, pou[2*MX][2*MX];
ll pref[2*MX][2*MX];
string A[2*MX], ans;

ll getp(int x1, int y1, int x2, int y2){
    return ((pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1])%MOD+MOD)%MOD;
}
bool same(int x1, int y1, int x2, int y2){
    ll tmp1=getp(x1, y1, x1+x2, y1+y2)*pou[ansx][ansy]%MOD, tmp2=getp(ansx, ansy, ansx+x2, ansy+y2)*pou[x1][y1]%MOD;
    tmp1=(tmp1+MOD)%MOD, tmp2=(tmp2+MOD)%MOD;
    return (tmp1==tmp2);
}

int main(){
    fastio;
    cin >> N >> M;
    for(int i=N; i>0; i--){
        string S;
        cin >> S;
        A[i]=S+S+" ";
        reverse(all(A[i]));
    }
    for(int i=1; i<=N; i++){
        A[N+i]=A[i];
    }
    for(int i=0; i<=2*N; i++){
        if(!i)
            pou[i][0]=1;
        else
            pou[i][0]=pou[i-1][0]*2%MOD;
        for(int j=1; j<=2*M; j++){
            pou[i][j]=pou[i][j-1]*3%MOD;
        }
    }
    for(int i=1; i<=2*N; i++){
        for(int j=1; j<=2*M; j++){
            (pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(A[i][j]=='.'?2:3)*pou[i][j])%=MOD;
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(same(i, j, N-1, M-1))
                continue;
            int le=0, ri=N-1, mi, x=-1, y=1;
            while(le<=ri){
                mi=(le+ri)/2;
                if(same(i, j, mi, M-1))
                    le=mi+1;
                else{
                    ri=mi-1;
                    x=mi;
                }
            }
            le=0, ri=M-1;
            while(le<=ri){
                mi=(le+ri)/2;
                if(same(i, j, x, mi))
                    le=mi+1;
                else{
                    ri=mi-1;
                    y=mi;
                }
            }
            if(A[i+x][j+y]>A[ansx+x][ansy+y])
                ansx=i, ansy=j;
        }
    }

    for(int i=N-1; i>=0; i--){
        for(int j=M-1; j>=0; j--){
            cout << A[ansx+i][ansy+j];
        }
        cout << nl;
    }
}

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