제출 #1232852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232852		nhq0914	Sateliti (COCI20_satellti)	C++17	110 / 110	361 ms	20928 KiB

Main

//a person woke up at the bottom of the abyss...

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
using namespace std;

// #ifdef my_local

// const int mod = 1e9 + 7;

// #else

// int rd_mod(int l, int r){
// 	function <bool(int)> is_prime = [&] (int n) {
// 		if(n == 2 || n == 3) return true;
// 		if(n < 3 || n % 2 == 0 || n % 3 == 0) return false;
// 		for (int i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;
// 		return true;
// 	};

// 	mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

// 	int num_mod = l + mt() % (r - l + 1);
// 	while(not is_prime(num_mod)) ++num_mod;
// 	return num_mod;
// }
 
// const int mod = rd_mod(1e9, 1.5e9);

// #endif

template <int _mod>
struct modint {
	constexpr static int mod = _mod;

	int m;

	modint(int n = 0) : m(n) {}
	modint(int64_t n) : m(n % mod) {}

	inline modint operator += (const modint &x) {
		m += x.m;
		if(m >= mod) m -= mod;
		return *this;
	}
	inline modint operator -= (const modint &x) {
		m -= x.m;
		if(m < 0) m += mod;
		return *this;
	}
	inline modint operator *= (const modint &x) {
		m = 1ll * m * x.m % mod;
		return *this;
	}
	inline modint operator /= (const modint &x) {
		return *this *= x.inv();
	}
	inline modint operator ^= (int p) {
		modint res = 1;
		while(p) {
			if(p & 1) res *= *this;
			*this *= *this;
			p >>= 1;
		}
		return res;
	}

	modint inv() const {
		modint t = *this;
		return t ^= (mod - 2);
	}

	inline friend modint operator + (modint x, const modint &y) {return x += y;}
	inline friend modint operator - (modint x, const modint &y) {return x -= y;}
	inline friend modint operator * (modint x, const modint &y) {return x *= y;}
	inline friend modint operator / (modint x, const modint &y) {return x /= y;}
	inline friend modint operator ^ (modint x, const int &y) {return x ^= y;}

	constexpr explicit operator bool () const {return m != 0;}
	constexpr bool operator == (const modint &x) const {return m == x.m;}
	constexpr bool operator != (const modint &x) const {return m != x.m;}
	friend std::istream &operator >> (std::istream &in, modint &x) {int64_t n; in >> n; x = modint(n); return in;}
	constexpr friend std::ostream &operator << (std::ostream &out, const modint &x) {out << x.m; return out;}
};

using mint = modint <(int)1e9 + 7>;

int n, m;
int ans_x, ans_y;
mint base_c = 29, base_r = 31;
mint pow_c[2001], pow_r[2001];
mint char_hash[2001][2001];
char a[2001][2001];

inline int w(char c) {
	if(c == '.') return 9;
	else return 11;
}

inline mint get_hash(int a, int b, int c, int d) {
	return char_hash[c][d] -
	char_hash[c][b - 1] * pow_c[d - b + 1] -
	char_hash[a - 1][d] * pow_r[c - a + 1] +
	char_hash[a - 1][b - 1] * pow_c[d - b + 1] * pow_r[c - a + 1];
}

int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	F(i, 1, n) F(j, 1, m) cin >> a[i][j];
	F(i, n + 1, 2 * n) F(j, 1, m) a[i][j] = a[i - n][j];
	F(i, 1, n) F(j, m + 1, 2 * m) a[i][j] = a[i][j - m];
	F(i, n + 1, 2 * n) F(j, m + 1, 2 * m) a[i][j] = a[i - n][j - m];
	// F(i, 1, 2 * n) {
	// 	F(j, 1, 2 * m) cout << a[i][j];
	// 	cout << '\n';
	// }
	pow_r[0] = 1, pow_c[0] = 1;;
	F(i, 1, 2 * n) pow_r[i] = base_r * pow_r[i - 1];
	F(i, 1, 2 * m) pow_c[i] = base_c * pow_c[i - 1];
	F(i, 1, 2 * n) {
		mint cur_hash = 0;
		F(j, 1, 2 * m) {
			cur_hash = base_c * cur_hash + w(a[i][j]);
			char_hash[i][j] = base_r * char_hash[i - 1][j] + cur_hash;
		}
	}
	ans_x = n;
	ans_y = m;
	F(i, n, 2 * n) F(j, m, 2 * m) {
		static int l, r, mid, row, col;
		l = i - n + 1, r = i, row = -1;
		while(l <= r) {
			mid = (l + r) / 2;
			if(get_hash(ans_x - n + 1, ans_y - m + 1, ans_x - i + mid, ans_y) == get_hash(i - n + 1, j - m + 1, mid, j))
				l = mid + 1;
			else r = mid - 1, row = mid;
		}
		if(row == -1) continue;
		l = j - m + 1, r = j, col = -1;
		while(l <= r) {
			mid = (l + r) / 2;
			if(get_hash(ans_x - n + 1, ans_y - m + 1, ans_x - i + row, ans_y - j + mid) == get_hash(i - n + 1, j - m + 1, row, mid))
				l = mid + 1;
			else r = mid - 1, col = mid;
		}
		if(col == -1) continue;
		if(a[row][col] < a[ans_x - i + row][ans_y - j + col])
			ans_x = i, ans_y = j;
	}
	F(i, ans_x - n + 1, ans_x) {
		F(j, ans_y - m + 1, ans_y) cout << a[i][j];
		cout << '\n';
	}
	cerr << "runtime: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
}

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