Submission #538061

#	Time	Username	Problem	Language	Result	Execution time	Memory
538061		skittles1412	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	1571 ms	212 KiB

necklace

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

namespace s1 {

bool eqr(string s, const string &t) {
	for (int i = 0; i < sz(s); i++) {
		if (s == t) {
			return true;
		}
		rotate(s.begin(), s.begin() + 1, s.end());
	}
	return false;
}

bool eq(string s, const string &t) {
	if (eqr(s, t)) {
		return true;
	}
	reverse(begin(s), end(s));
	return eqr(s, t);
}

void solve(const string &s, const string &t) {
	int n = sz(s), m = sz(t);
	array<int, 3> ans {};
	for (int i = 1; i <= n; i *= 2) {
		for (int j = 0; j + i <= n; j++) {
			for (int k = 0; k + i <= m; k++) {
				if (eq(s.substr(j, i), t.substr(k, i))) {
					ans = {i, j, k};
				}
			}
		}
	}
	auto [a, b, c] = ans;
	cout << a << endl;
	cout << b << " " << c << endl;
}

}

constexpr long bpow(long base, long exp, long mod) {
	long ans = 1;
	while (exp) {
		if (exp & 1) {
			ans = (ans * base) % mod;
		}
		exp >>= 1;
		base = (base * base) % mod;
	}
	return ans;
}

constexpr long inv(long x, long mod) {
	return bpow(x, mod - 2, mod);
}

template <long base, long mod>
struct Pow {
	static constexpr int maxn = 3e3 + 5;
	long arr[maxn];

	constexpr Pow() : arr() {
		arr[0] = 1;
		for (int i = 1; i < maxn; i++) {
			arr[i] = (arr[i - 1] * base) % mod;
		}
	}

	long operator[](int i) const {
		return arr[i];
	}
};

template <long base, long mod>
struct Hasher {
	static constexpr long ibase = inv(base, mod);
	static constexpr Pow<base, mod> pow {};
	static constexpr Pow<ibase, mod> ipow {};
	vector<long> psum;

	explicit Hasher(const string& s) : psum(sz(s) + 1) {
		for (int i = 0; i < sz(s); i++) {
			psum[i + 1] = (psum[i] + (s[i] - 'a' + 1) * pow[i]) % mod;
		}
	}

	long hash(int l, int r) const {
		return (psum[r] - psum[l] + mod) * ipow[l] % mod;
	}

	long merge(int len, long a, long b) const {
		return (a + b * pow[len]) % mod;
	}

	long rot(int len, long h) const {
		long x = h % base;
		return ((h - x + mod) * ibase + x * pow[len - 1]) % mod;
	}
};

const long base = 31, base2 = 29, mod = 1e9 + 7;

tuple<int, int, int> solve(const string& s, const string& t) {
	Hasher<base, mod> hs(s), ht(t);
	Hasher<base2, mod> hs2(s), ht2(t);
	int n = sz(s), m = sz(t);
	for (int i = n; i >= 1; i--) {
		map<pair<long, long>, int> cur, cur2;
		for (int j = 0; j + i <= m; j++) {
			cur[{ht.hash(j, j + i), ht2.hash(j, j + i)}] = j;
		}
		for (int j = 0; j + i <= n; j++) {
			for (int k = 0; k < i; k++) {
				long x = hs.merge(i - k, hs.hash(j + k, j + i), hs.hash(j, j + k));
				long x2 = hs2.merge(i - k, hs2.hash(j + k, j + i), hs2.hash(j, j + k));
				auto it = cur.find({x, x2});
				if (it != cur.end()) {
					return {i, j, it->second};
				}
			}
		}
	}
	assert(false);
}

void solve() {
	{
		Hasher<base, mod> tmp("bcbcccb"), tmp1("cbcccbb");
		long x = tmp.hash(0, 7);
		for (int i = 0; i < 7; i++) {
			x = tmp.rot(7, x);
			dbg(x);
		}
		dbg(tmp1.hash(0, 7));
	}
	string s, t;
	cin >> s >> t;
	if (max(sz(s), sz(t)) > 400) {
		s1::solve(s, t);
		return;
	}
	auto [x, a, b] = solve(s, t);
	reverse(begin(s), end(s));
	auto [x1, a1, b1] = solve(s, t);
	dbg(x, a, b, x1, a1, b1);
	if (x1 > x) {
		x = x1;
		a = sz(s) - a1 - x;
		b = b1;
	}
	cout << x << endl;
	cout << a << " " << b << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

• Subtask 1: 0 / 15