oj.uz

답안 #633958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633958 2022-08-23T13:57:35 Z vovamr Sateliti (COCI20_satellti) C++17
110 / 110
 698 ms 54496 KB 
#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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15976 KB Output is correct
2 Correct 17 ms 16028 KB Output is correct
3 Correct 18 ms 15976 KB Output is correct
4 Correct 18 ms 16012 KB Output is correct
5 Correct 22 ms 15988 KB Output is correct
6 Correct 21 ms 15980 KB Output is correct
7 Correct 19 ms 16000 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15976 KB Output is correct
2 Correct 17 ms 16028 KB Output is correct
3 Correct 18 ms 15976 KB Output is correct
4 Correct 18 ms 16012 KB Output is correct
5 Correct 22 ms 15988 KB Output is correct
6 Correct 21 ms 15980 KB Output is correct
7 Correct 19 ms 16000 KB Output is correct
8 Correct 61 ms 19296 KB Output is correct
9 Correct 21 ms 16076 KB Output is correct
10 Correct 18 ms 16100 KB Output is correct
11 Correct 60 ms 19276 KB Output is correct
12 Correct 63 ms 19356 KB Output is correct
13 Correct 63 ms 19444 KB Output is correct
14 Correct 75 ms 19412 KB Output is correct
15 Correct 63 ms 19404 KB Output is correct
16 Correct 72 ms 19412 KB Output is correct
17 Correct 65 ms 19412 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15976 KB Output is correct
2 Correct 17 ms 16028 KB Output is correct
3 Correct 18 ms 15976 KB Output is correct
4 Correct 18 ms 16012 KB Output is correct
5 Correct 22 ms 15988 KB Output is correct
6 Correct 21 ms 15980 KB Output is correct
7 Correct 19 ms 16000 KB Output is correct
8 Correct 61 ms 19296 KB Output is correct
9 Correct 21 ms 16076 KB Output is correct
10 Correct 18 ms 16100 KB Output is correct
11 Correct 60 ms 19276 KB Output is correct
12 Correct 63 ms 19356 KB Output is correct
13 Correct 63 ms 19444 KB Output is correct
14 Correct 75 ms 19412 KB Output is correct
15 Correct 63 ms 19404 KB Output is correct
16 Correct 72 ms 19412 KB Output is correct
17 Correct 65 ms 19412 KB Output is correct
18 Correct 648 ms 54256 KB Output is correct
19 Correct 24 ms 16604 KB Output is correct
20 Correct 26 ms 16724 KB Output is correct
21 Correct 603 ms 54396 KB Output is correct
22 Correct 685 ms 54396 KB Output is correct
23 Correct 636 ms 54404 KB Output is correct
24 Correct 684 ms 54496 KB Output is correct
25 Correct 608 ms 54468 KB Output is correct
26 Correct 698 ms 54404 KB Output is correct
27 Correct 687 ms 54332 KB Output is correct