oj.uz

Submission #537405

# Submission time Handle Problem Language Result Execution time Memory
537405 2022-03-15T04:59:19 Z Stro256 Sateliti (COCI20_satellti) C++14
110 / 110
 562 ms 35028 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define rep(i,a,b) FOR(i,a,b)
#define REP(a) F0R(_,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rsz resize
#define pb push_back
#define f first
#define s second
#define pf push_front
#define ft front()
#define bk back()
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define tcT template<class T
#define tcTU tcT, class U
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pi = pair<int,int>;
using vpi = vector<pi>;
using str = string;
using vs = vector<str>;
using db = long double;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
tcTU> using PR = pair<T,U>;
tcT, int SZ> using AR = array<T, SZ>;

const int MOD = 1e9+7;
const ll INF = 1e18;
const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};

constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr bool onbit(int msk, int i) { return msk>>i&1; }
constexpr ll p2(int x) { return 1LL<<x; }
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int lg2(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }; //int only

tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b,1 : 0; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }

tcTU> T fstTrue(T lo, T hi, U f) {
    hi++; assert(lo <= hi);
    while (lo < hi) {
        T mid = lo+(hi-lo)/2;
        f(mid) ? hi = mid : lo = mid+1;
    }
    return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
    lo--; assert(lo <= hi);
    while (lo < hi) {
        T mid = lo+(hi-lo+1)/2;
        f(mid) ? lo = mid : hi = mid-1;
    }
    return lo;
}

tcT> void remDup(V<T> &v) {
    sort(all(v)); v.erase(unique(all(v)), end(v)); }
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

void setPrec() { cout << fixed << setprecision(16); }
void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    setPrec();
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

const int MX = 1e3+10;
int N, M;
const int P = 2, Q = 3;
int PQpow[2*MX][2*MX];
int hs[2*MX][2*MX];

int add(int a, int b) {
    if((a += b) >= MOD) a-=MOD;
    return a;
}

int sub(int a, int b) { return add(a, MOD-b); }

int mul(int a, int b) {
    return 1LL*a*b%MOD;
}

int getHash(int x, int y, int dx, int dy) {
    return add(sub(hs[x+dx][y+dy], add(hs[x+dx][y], hs[x][y+dy])), hs[x][y]);
}

int eq(int x1, int y1, int x2, int y2, int dx, int dy) {
    return mul(getHash(x1, y1, dx, dy), PQpow[x2][y2]) == mul(getHash(x2, y2, dx, dy), PQpow[x1][y1]);
}

str S[MX];

void solve() {
    cin>>N>>M;
    F0R(i,N) cin>>S[i];
    F0R(i,2*N) F0R(j,2*M) {
        if(i == 0 && j == 0) PQpow[i][j] = 1;
        else if(j == 0) PQpow[i][j] = mul(PQpow[i-1][j],P);
        else PQpow[i][j] = mul(PQpow[i][j-1], Q);
    }
    F0R(i,2*N) F0R(j,2*M) {
        hs[i+1][j+1] = mul(S[i%N][j%M] == '.', PQpow[i][j]);
        hs[i+1][j+1] = sub(add(hs[i+1][j+1], add(hs[i][j+1], hs[i+1][j])), hs[i][j]);
    }
    int ansx, ansy;
    ansx = ansy = 0;
    F0R(i,N) F0R(j,M) {
        int lo = 0, hi = N;
        while(lo<hi) {
            int mid = lo + (hi-lo+1)/2;
            if(eq(ansx, ansy, i, j, mid, M)) lo = mid;
            else hi = mid-1;
        }
        int dx, dy;
        dx = lo;
        lo = 0, hi = M;
        while(lo<hi) {
            int mid = lo + (hi-lo+1)/2;
            if(eq(ansx+dx, ansy, i+dx, j, 1, mid)) lo = mid;
            else hi = mid-1;
        }
        dy = lo;
        if(S[(i+dx)%N][(j+dy)%M] < S[(ansx+dx)%N][(ansy+dy)%M]) {
            ansx = i, ansy = j;
        }
    }
    F0R(i,N) F0R(j,M) {
        cout << S[(ansx+i)%N][(ansy+j)%M];
        if(j == M-1) cout << "\n";
    }

}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 37 ms 7920 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 42 ms 7920 KB Output is correct
12 Correct 42 ms 8144 KB Output is correct
13 Correct 55 ms 8228 KB Output is correct
14 Correct 45 ms 8172 KB Output is correct
15 Correct 37 ms 8272 KB Output is correct
16 Correct 45 ms 8188 KB Output is correct
17 Correct 43 ms 8172 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 37 ms 7920 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 42 ms 7920 KB Output is correct
12 Correct 42 ms 8144 KB Output is correct
13 Correct 55 ms 8228 KB Output is correct
14 Correct 45 ms 8172 KB Output is correct
15 Correct 37 ms 8272 KB Output is correct
16 Correct 45 ms 8188 KB Output is correct
17 Correct 43 ms 8172 KB Output is correct
18 Correct 445 ms 35004 KB Output is correct
19 Correct 12 ms 16724 KB Output is correct
20 Correct 8 ms 1012 KB Output is correct
21 Correct 412 ms 34980 KB Output is correct
22 Correct 502 ms 34912 KB Output is correct
23 Correct 459 ms 35020 KB Output is correct
24 Correct 493 ms 34912 KB Output is correct
25 Correct 464 ms 35028 KB Output is correct
26 Correct 562 ms 35000 KB Output is correct
27 Correct 492 ms 34864 KB Output is correct