Submission #1103613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103613		fonikos01	Sateliti (COCI20_satellti)	C++17	50 / 110	3071 ms	157856 KiB

Main

#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>
 
// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;
 
using namespace std;
const int LARGE = 1e9;
 
#define all(x) (x).begin(), (x).end()
 
using ll = long long;
typedef pair<ll, ll> pi;
 
// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
//         if (a.second < b.second)
//                 return true;
//         return false;
// }
// struct node
// {
//         // part which will store data
//         int data;
//         // pointer to the previous node
//         struct node *prev;
//         // pointer to the next node
//         struct node *next;
// };
// struct trienode
// {
//         vector<trienode*> desc;
//         vector<ll> descExist;
 
//         trienode(ll M) {
//                 desc.resize(M);
//                 descExist.resize(M);
//         }
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// 	static const int mod = MOD;
// 	static constexpr mint rt() { return RT; } // primitive root
//  	int v;
//  	explicit operator int() const { return v; }
// 	mint():v(0) {}
// 	mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// 	mint& operator+=(mint o) {
// 		if ((v += o.v) >= MOD) v -= MOD;
// 		return *this; }
// 	mint& operator-=(mint o) {
// 		if ((v -= o.v) < 0) v += MOD;
// 		return *this; }
// 	mint& operator*=(mint o) {
// 		v = int((ll)v*o.v%MOD); return *this; }
// 	friend mint pow(mint a, ll p) { assert(p >= 0);
// 		return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// 	friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// 	friend mint operator+(mint a, mint b) { return a += b; }
// 	friend mint operator-(mint a, mint b) { return a -= b; }
// 	friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;
 
struct mySeg
{
        vector<ll> A;
        ll N;
 
        void build()
        {
                A.resize(N * 2);
                for (int i = 0; i < N; i++)
                        A[i + N] = A[i];
                for (int i = N - 1; i > 0; i--)
                        A[i] = min(A[i << 1], A[i << 1 ^ 1]);
                // for (auto el : A) cout << el << " ";
        }
 
        void set(ll idx, ll val)
        {
                idx += N;
                A[idx] = val;
                for (int i = idx >> 1; i > 0; i >>= 1)
                        A[i] = min(A[i << 1], A[i << 1 ^ 1]);
                // for (auto el : A) cout << el << " ";
        }
 
        ll minnQuery(ll l, ll r)
        {
                ll minn = INT64_MAX;
                for (l = l + N, r = r + N; l < r; l >>= 1, r >>= 1)
                {
                        if (l % 2)
                                minn = min(minn, A[l++]);
                        if (r % 2)
                                minn = min(minn, A[--r]);
                }
                return minn;
        }
};
 
 
// template <class T>
// class myFen
// {
// private:
//         int N;
//         vector<T> A;
//         vector<T> BIT;
 
// public:
//         myFen(int size) : N(size), A(size + 1), BIT(size + 1) {}
 
//         void set(ll idx, ll val)
//         {
//                 update(idx, val - A[idx]);
//                 A[idx] = val;
//         }
//         void update(ll idx, ll diff)
//         {
//                 for (idx = idx; idx <= N; idx += idx & (-idx))
//                         BIT[idx] += diff;
//         }
//         ll sumQuery(ll idx)
//         {
//                 if (idx == 0)
//                         return 0LL;
//                 ll summ = 0;
//                 for (idx = idx; idx > 0; idx -= idx & (-idx))
//                         summ += BIT[idx];
//                 return summ;
//         }
// };
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
 
// class HashedString {
//   private:
// 	// change M and B if you want
// 	static const ll M = (1LL << 61) - 1;
// 	static const ll B;
 
// 	// pow[i] contains B^i % M
// 	static vector<ll> pow;
 
// 	// p_hash[i] is the hash of the first i characters of the given string
// 	vector<ll> p_hash;
 
// 	__int128 mul(ll a, ll b) { return (__int128)a * b; }
// 	ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
 
//   public:
// 	HashedString(const string &s) : p_hash(s.size() + 1) {
// 		while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
// 		p_hash[0] = 0;
// 		for (int i = 0; i < s.size(); i++) {
// 			p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
// 		}
// 	}
 
// 	ll get_hash(int start, int end) {
// 		ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
// 		return (raw_val + M) % M;
// 	}
// };
// mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// vector<ll> HashedString::pow = {1};
// const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
ll power(ll x, ll y, ll M)
{
    if (y == 0)
        return ll(1);
 
    ll p = power(x, y / ll(2), M) % M;
    p = (p * p) % M;
 
    return (y % ll(2) == 0) ? p : (x * p) % M;
}
 
ll solve()
{
        ll N, M; cin >> N >> M;
 
        vector<vector<ll>> A(N*2, vector<ll>(0));
 
        for (int i = 0; i < N; i++) {
                string S; cin >> S;
                for (int j = 0; j < M; j++) {
                        if (S[j] == '.') A[i].push_back(1);
                        else A[i].push_back(0);
                }
                for (int j = 0; j < M; j++) {
                        A[i].push_back(A[i][j]);
                }
        }
        for (int i = 0; i < N; i++) {
                for (int j = 0; j < M*2; j++) {
                        A[N+i].push_back(A[i][j]);
                }
        }
        N *= 2, M *= 2;
        vector<vector<ll>> PSHASH1(N+1, vector<ll>(M+1));
        vector<vector<ll>> PSHASH1ROW(N+1, vector<ll>(M+1));
        vector<vector<ll>> PSHASH2(N+1, vector<ll>(M+1));
        vector<vector<ll>> PSHASH2ROW(N+1, vector<ll>(M+1));
 
        ll MOD = (1LL<<31)-1;
        ll p1 = 2, p2 = 5, q1 = 3, q2 = 7;
        vector<ll> powp1(N+1);vector<ll> powp2(N+1);vector<ll> powq1(M+1);vector<ll> powq2(M+1);
        powp1[0] = powp2[0] = powq1[0] = powq2[0] = 1;
        for (int i = 1; i <= N; i++) {
                powp1[i] = (__int128)powp1[i-1]*p1%MOD;
                powp2[i] = (__int128)powp2[i-1]*p2%MOD;
        }
        for (int j = 1; j <= M; j++) {
                powq1[j] = (__int128)powq1[j-1]*q1%MOD;
                powq2[j] = (__int128)powq2[j-1]*q2%MOD;
        }
        function<ll(ll, ll)> addMod = [&](ll a, ll b) {
                ll val = ((__int128)a+b)%MOD;
                return val;
        };
        function<ll(ll, ll)> subMod = [&](ll a, ll b) {
                ll val = ((__int128)a-b+MOD)%MOD;
                return val;
        };
        // ll test = ((__int128)(1LL<<62)+(1LL<<62)+(1LL<<62)+(1LL<<62)+(1LL<<62))%MOD;
        // cout << test << '\n';
        // cout << MOD << '\n';
        // cout << (1LL<<61) << '\n';
        // cout << 1LL-(1LL<<62)-(1LL<<62) << '\n';
        // cout << (subMod(1LL,(1LL<<55))) << '\n';
        for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                        ll hash1 = (__int128)A[i-1][j-1]*powp1[i-1]%MOD*powq1[j-1]%MOD;
                        ll hash2 = (__int128)A[i-1][j-1]*powp2[i-1]%MOD*powq2[j-1]%MOD;
                        PSHASH1[i][j] = addMod(subMod(addMod(PSHASH1[i-1][j],PSHASH1[i][j-1]),PSHASH1[i-1][j-1]),hash1);
                        PSHASH2[i][j] = addMod(subMod(addMod(PSHASH2[i-1][j],PSHASH2[i][j-1]),PSHASH2[i-1][j-1]),hash2);
                        PSHASH1ROW[i][j] = addMod(PSHASH1ROW[i][j-1],hash1);
                        PSHASH2ROW[i][j] = addMod(PSHASH2ROW[i][j-1],hash2);
                }
        }
 
        

        ll bestI = 1, bestJ = 1;
        ll opCNt = 0;
        for (int i = 1; i <= N/2; i++) {
                for (int j = 1; j <= M/2; j++) {
                        if (i == 1 && j == 1) continue;
                        ll l = 1, r = N/2*M/2;
                        while (l <= r) {
                                opCNt++;
                                ll m = l+(r-l)/2;
                                ll rowCnt = m/(M/2)+(m%(M/2)==0?-1:0);
                                ll remm = m%(M/2);
                                if (remm == 0) remm = M/2;
                                ll x1 = bestI+rowCnt, y1 = bestJ+(M/2)-1; 
                                ll x2 = i+rowCnt, y2 = j+(M/2)-1;
                                ll besthash1 = subMod(addMod(subMod(subMod(PSHASH1[x1][y1],PSHASH1[x1][bestJ-1]),PSHASH1[bestI-1][y1]),PSHASH1[bestI-1][bestJ-1]),subMod(PSHASH1ROW[x1][y1],PSHASH1ROW[x1][bestJ+remm-1]));
                                ll besthash2 = subMod(addMod(subMod(subMod(PSHASH2[x1][y1],PSHASH2[x1][bestJ-1]),PSHASH2[bestI-1][y1]),PSHASH2[bestI-1][bestJ-1]),subMod(PSHASH2ROW[x1][y1],PSHASH2ROW[x1][bestJ+remm-1]));
                                ll currhash1 = subMod(addMod(subMod(subMod(PSHASH1[x2][y2],PSHASH1[x2][j-1]),PSHASH1[i-1][y2]),PSHASH1[i-1][j-1]),subMod(PSHASH1ROW[x2][y2],PSHASH1ROW[x2][j+remm-1]));
                                ll currhash2 = subMod(addMod(subMod(subMod(PSHASH2[x2][y2],PSHASH2[x2][j-1]),PSHASH2[i-1][y2]),PSHASH2[i-1][j-1]),subMod(PSHASH2ROW[x2][y2],PSHASH2ROW[x2][j+remm-1]));

                                if (bestI < i) {
                                        besthash1 = (__int128)besthash1*powp1[i-bestI]%MOD;
                                        besthash2 = (__int128)besthash2*powp2[i-bestI]%MOD;
                                } else {
                                        currhash1 = (__int128)currhash1*powp1[bestI-i]%MOD;
                                        currhash2 = (__int128)currhash2*powp2[bestI-i]%MOD;
                                }
                                if (bestJ < j) {
                                        besthash1 = (__int128)besthash1*powq1[j-bestJ]%MOD;
                                        besthash2 = (__int128)besthash2*powq2[j-bestJ]%MOD;
                                } else {
                                        currhash1 = (__int128)currhash1*powq1[bestJ-j]%MOD;
                                        currhash2 = (__int128)currhash2*powq2[bestJ-j]%MOD;
                                }
                                // if (i == 35 && j == 15) {
                                //         cout << "m " << m << '\n';
                                //         cout << "besthashs " << besthash1 << " " << besthash2 << '\n';
                                //         cout << "currhashs " << currhash1 << " " << currhash2 << '\n';
                                // }
                                if (besthash1 == currhash1 && besthash2 == currhash2) l = m+1;
                                else r = m-1;
                        }
                        if (l <= N/2*M/2) {
                                ll rowCnt = l/(M/2)+(l%(M/2)==0?-1:0);
                                ll remm = l%(M/2);
                                if (remm == 0) remm = M/2;
                                ll bestX = bestI+rowCnt, bestY = bestJ+remm-1;
                                bestX--;bestY--;
                                if (A[bestX][bestY] == 1) {
                                        bestI = i;
                                        bestJ = j;
                                }
                        }
                }
        }
 
        for (int i = 0; i < N/2; i++) {
                for (int j = 0; j < M/2; j++) {
                        if (A[bestI+i-1][bestJ+j-1] == 0) cout << '*';
                        else cout << '.';
                }
                cout << '\n';
        }
        // cout << "OPCNT " << opCNt << '\n';
        return 0;
}
 
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        // freopen("paintbarn2.in", "r", stdin);
        // freopen("paintbarn2.out", "w", stdout);
 
        // ll caseCnt = 1;
 
        // ll T;
        // cin >> T;
        // while (T--)
        // {
 
        solve();
 
        // 	cout << "Case #"<< caseCnt << ": " << ans << '\n';
        // 	caseCnt++;
        // }
 
        return 0;
}

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