Submission #873053

#	Time	Username	Problem	Language	Result	Execution time	Memory
873053		Trisanu_Das	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	66 ms	11100 KiB

necklace

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;
 
const ll MAXN = 400 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll p, p_pow[MAXN], hsh[4][MAXN][MAXN], cyc_hsh[4][MAXN][MAXN];
string s1, s1_r, s2;
 
ll CycHash(int ind, int L, int R) {
	ll ans = 0;
	for (int i = L; i <= R; i++) {
		ll h = (hsh[ind][i + 1][R] + hsh[ind][L][i] * p_pow[R - i]) % MOD;
		ans ^= h;
	}
 
	return ans;
}
 
 
void RollHash(string s, int ind) {	
	int n = s.size();
	for (int L = 1; L <= n; L++) {
		for (int R = L; R <= n; R++) {
			int x = (s[R - 1] - 'a');
			hsh[ind][L][R] = (hsh[ind][L][R - 1] + p_pow[R - L] * x) % MOD;
		}
	}
 
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
		       cyc_hsh[ind][i][j] = CycHash(ind, i, j);	
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s1 >> s2;
	s1_r = s1;
	reverse(all(s1_r));
 
	p = rng() % MOD;
	p_pow[0] = 1;
	for (int i = 1; i < MAXN; i++) p_pow[i] = p_pow[i - 1] * p % MOD;
 
	RollHash(s1, 0);
	RollHash(s1_r, 1);
	RollHash(s2, 2);
	
	for (int i = min(s1.size(), s2.size()); i > 0; i--) {
		for (int L1 = 1; L1 <= s1.size() - i + 1; L1++) {
			for (int L2 = 1; L2 <= s2.size() - i + 1; L2++) {
				int R1 = L1 + i - 1, R2 = L2 + i - 1, n = s1.size();
				ll hsh = cyc_hsh[2][L2][R2];
			       	ll hsh1 = cyc_hsh[0][L1][R1], hsh2 = cyc_hsh[1][n - R1 + 1][n - L1 + 1];
				if (hsh == hsh1 || hsh == hsh2) return cout << i << endl << L1 - 1 << sep << L2 - 1 << endl, 0;	
			}
		}
	}
	return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int L1 = 1; L1 <= s1.size() - i + 1; L1++) {
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
necklace.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for (int L2 = 1; L2 <= s2.size() - i + 1; L2++) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40