oj.uz

Submission #557246

# Submission time Handle Problem Language Result Execution time Memory
557246 2022-05-05T02:15:49 Z CyberSleeper Sateliti (COCI20_satellti) C++17
110 / 110
 603 ms 69300 KB 
#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=1000000009, 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, ansx=1, ansy=1, pou[2*MX][2*MX];
ll pref[2*MX][2*MX];
string A[2*MX];

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=1; i<=N; i++){
        cin >> A[i];
        A[i]=" "+A[i]+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]*3%MOD;
        for(int j=1; j<=2*M; j++){
            pou[i][j]=pou[i][j-1]*5%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]=='*'?3:5)*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=0; i<N; i++){
        for(int j=0; j<M; j++){
            cout << A[ansx+i][ansy+j];
        }
        cout << nl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1304 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1304 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 41 ms 10964 KB Output is correct
9 Correct 2 ms 788 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 42 ms 10956 KB Output is correct
12 Correct 46 ms 11128 KB Output is correct
13 Correct 44 ms 11336 KB Output is correct
14 Correct 58 ms 11320 KB Output is correct
15 Correct 55 ms 11300 KB Output is correct
16 Correct 57 ms 11320 KB Output is correct
17 Correct 46 ms 11324 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1304 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 41 ms 10964 KB Output is correct
9 Correct 2 ms 788 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 42 ms 10956 KB Output is correct
12 Correct 46 ms 11128 KB Output is correct
13 Correct 44 ms 11336 KB Output is correct
14 Correct 58 ms 11320 KB Output is correct
15 Correct 55 ms 11300 KB Output is correct
16 Correct 57 ms 11320 KB Output is correct
17 Correct 46 ms 11324 KB Output is correct
18 Correct 513 ms 69116 KB Output is correct
19 Correct 13 ms 17236 KB Output is correct
20 Correct 8 ms 1620 KB Output is correct
21 Correct 480 ms 69196 KB Output is correct
22 Correct 538 ms 69256 KB Output is correct
23 Correct 522 ms 69196 KB Output is correct
24 Correct 542 ms 69200 KB Output is correct
25 Correct 452 ms 69196 KB Output is correct
26 Correct 524 ms 69300 KB Output is correct
27 Correct 603 ms 69208 KB Output is correct