oj.uz

Submission #525527

# Submission time Handle Problem Language Result Execution time Memory
525527 2022-02-11T21:34:05 Z Yazan_Alattar Necklace (Subtask 1-3) (BOI19_necklace1) C++14
5 / 85
 1500 ms 106556 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
 
struct Hash {
	ll SEED = 57,MOD = 1e9 + 7;
	vector<ll> ha;
	vector<ll> power;
 
	void build(string x) {
		power.resize(x.size());
		ha.resize(x.size());
		power[0] = 1;
		for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
		ha[0] = x[0];
		for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
	}
	void Add(string x)
	{
		for(int i = 0; i < x.size(); i++)   power.push_back((power.back() * SEED)%MOD);
		for(int i = 0; i < x.size(); i++)   ha.push_back((ha.back() * SEED + x[i])%MOD);
	}
	ll get(int i, int j, int len) {
		if(j < i) return 0;
		ll ret = ha[j];
		if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
		ret = (ret % MOD + MOD) % MOD;
		return ret * power[len];
	}
};
 
ll ans, ansi, ansj;
string s, t;
map <ll, ll> mp;
 
int main()
{
	cin >> s >> t;
	Hash Hs, Ht; Hs.build(s); Ht.build(t);
	int n = s.size(), m = t.size(); 
	for(int i = 0; i < n; ++i){
		for(int j = i; j < n; ++j){
			for(int k = i; k <= j; ++k){
				mp[Hs.get(k, j, k - i) + Hs.get(i, k - 1, 0)] = i + 1;
			}
		}
	}
	for(int i = 0; i < m; ++i){
		for(int j = i; j < m; ++j){
			if(mp[Ht.get(i, j, 0)] && j - i + 1 > ans){
				ans = j - i + 1;
				ansi = mp[Ht.get(i, j, 0)] - 1;
				ansj = i;
			}
		}
	}
	
	reverse(all(t));
	Hash Hrt; Hrt.build(t);
	for(int i = 0; i < m; ++i){
		for(int j = i; j < m; ++j){
			if(mp[Hrt.get(i, j, 0)] && j - i + 1 > ans){
				ans = j - i + 1;
				ansi = mp[Hrt.get(i, j, 0)] - 1;
				ansj = m - j - 1;
			}
		}
	}
	
	cout << ans << endl << ansi << " " << ansj << endl;
	return 0;
}

Compilation message

necklace.cpp: In member function 'void Hash::Add(std::string)':
necklace.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i = 0; i < x.size(); i++)   power.push_back((power.back() * SEED)%MOD);
      |                  ~~^~~~~~~~~~
necklace.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i = 0; i < x.size(); i++)   ha.push_back((ha.back() * SEED + x[i])%MOD);
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 44 ms 5708 KB Output is partially correct
2 Partially correct 42 ms 5220 KB Output is partially correct
3 Partially correct 28 ms 5768 KB Output is partially correct
4 Partially correct 74 ms 10580 KB Output is partially correct
5 Partially correct 77 ms 10960 KB Output is partially correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 44 ms 5708 KB Output is partially correct
2 Partially correct 42 ms 5220 KB Output is partially correct
3 Partially correct 28 ms 5768 KB Output is partially correct
4 Partially correct 74 ms 10580 KB Output is partially correct
5 Partially correct 77 ms 10960 KB Output is partially correct
6 Execution timed out 1590 ms 106556 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 44 ms 5708 KB Output is partially correct
2 Partially correct 42 ms 5220 KB Output is partially correct
3 Partially correct 28 ms 5768 KB Output is partially correct
4 Partially correct 74 ms 10580 KB Output is partially correct
5 Partially correct 77 ms 10960 KB Output is partially correct
6 Execution timed out 1590 ms 106556 KB Time limit exceeded
7 Halted 0 ms 0 KB -