Submission #633958

#TimeUsernameProblemLanguageResultExecution timeMemory
633958vovamrSateliti (COCI20_satellti)C++17
110 / 110
698 ms54496 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } constexpr int md = 1e9 + 9; constexpr int iv2 = (md + 1) / 2; inline int add(int a, int b) { a += b; if(a>=md){a-=md;} return a; } inline int sub(int a, int b) { a -= b; if(a<0){a+=md;} return a; } inline int mul(int a, int b) { return (ll)a * b % md; } inline int bp(int a, int n) { int res = 1; for (; n; n >>= 1, a = mul(a, a)) { if (n & 1) res = mul(res, a); } return res; } inline int inv(int a) { return bp(a, md - 2); } const int N = 2e6 + 10; constexpr int p = 10039; int pw[N], ipw[N]; inline void calc() { const int ip = inv(p); pw[0] = ipw[0] = 1; for (int i = 1; i < N; ++i) { pw[i] = mul(pw[i - 1], p); ipw[i] = mul(ipw[i - 1], ip); } } inline void solve() { calc(); int n, m; cin >> n >> m; ve<ve<char>> a(n,ve<char>(m)); for (auto &i : a) for (auto &j : i) cin >> j; for (auto &i : a) for (auto &j : i) j = (j == '*' ? 'b' : 'c'); ve<ve<char>> c(2 * n, ve<char> (2 * m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { c[i][j] = a[i][j]; c[i + n][j] = a[i][j]; c[i][j + m] = a[i][j]; c[i + n][j + m] = a[i][j]; } } // cout << '\n'; // for (auto &i : c) { // for (auto &j : i) cout << j; // cout << '\n'; // } // cout << '\n'; ve<ve<int>> ha(2 * n, ve<int> (2 * m)); for (int i = 0; i < 2 * n; ++i) { ha[i][2 * m - 1] = (c[i][2 * m - 1] - 'a'); for (int j = 2 * m - 2; ~j; --j) { ha[i][j] = add(mul(p, ha[i][j + 1]), c[i][j] - 'a'); } } ve<ve<int>> val(2 * n, ve<int> (m)); for (int i = 0; i < 2 * n; ++i) { for (int j = 0; j < m; ++j) { val[i][j] = sub(ha[i][j], mul(pw[m], ha[i][j + m])); } } ve<ve<int>> tr(2 * n, ve<int> (m)); for (int j = 0; j < m; ++j) { tr[2 * n - 1][j] = val[2 * n - 1][j]; for (int i = 2 * n - 2; ~i; --i) { tr[i][j] = add(mul(pw[m], tr[i + 1][j]), val[i][j]); } } auto get = [&](int x, int y, int len) { int whole = len / m, r = len % m; int hash = 0; // [x, x + whole - 1] hash = sub(tr[x][y], mul(pw[whole * m], tr[x + whole][y])); int h = sub(ha[x + whole][y], mul(pw[r], ha[x + whole][y + r])); hash = add(hash, mul(pw[whole * m], h) ); return hash; }; auto compare = [&](int x1, int y1, int x2, int y2) { int l = 1, r = n * m, mid, ans = 0; while (l <= r) { mid = l + r >> 1; if (get(x1, y1, mid) == get(x2, y2, mid)) ans = mid, l = mid + 1; else r = mid - 1; } if (ans == n * m) return 0; else { char A = c[x1 + (ans / m)][y1 + (ans % m)]; char B = c[x2 + (ans / m)][y2 + (ans % m)]; return (A < B ? -1 : 1); } }; int x = 0, y = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!i && !j) continue; if (compare(i, j, x, y) == -1) tie(x, y) = mpp(i, j); } } // cout << '\n' << '\n'; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cout << (c[x + i][y + j] == 'b' ? '*' : '.'); } cout << '\n'; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |    mid = l + r >> 1;
      |          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...