Submission #633958

#	Time	Username	Problem	Language	Result	Execution time	Memory
633958		vovamr	Sateliti (COCI20_satellti)	C++17	110 / 110	698 ms	54496 KiB

Main

#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;
      |          ~~^~~

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