oj.uz

Submission #646408

# Submission time Handle Problem Language Result Execution time Memory
646408 2022-09-29T18:31:41 Z dozer Necklace (Subtask 1-3) (BOI19_necklace1) C++14
5 / 85
 1500 ms 86220 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define int long long

const int mod1 = 1e9 + 7, mod2 = 1e9 + 37, p1 = 37, p2 = 31;
int e1[N], e2[N];

int add(int a, int b, int m)
{
	if (a + b < m) return a + b;
	return a + b - m;
}

int subs(int a, int b, int m)
{
	if (a >= b) return a - b;
	return a - b + m;
}

int mul(int a, int b, int m)
{
	return (a * b) % m;
}

pair<int, pii> f(string s, string t)
{
	map<int, int> s1, s2;
	int n = s.size(), m = t.size();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < n - i + 1; j++)
		{
			vector<int> v;
			int val1 = 0, val2 = 0; 
			for (int k = j; k < j + i; k++)
			{
				val1 = add(val1, mul(s[k] - 'a' + 1, e1[k - j], mod1), mod1);
				val2 = add(val2, mul(s[k] - 'a' + 1, e2[k - j], mod2), mod2);
				v.pb({s[k] - 'a' + 1});
			}
			reverse(v.begin(), v.end());
			for (auto k : v)
			{
				val1 = subs(val1, mul(k, e1[i - 1], mod1), mod1);
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, k, mod1);
				val2 = subs(val2, mul(k, e2[i - 1], mod2), mod2);
				val2 = mul(val2, p2, mod2);
				val2 = add(val2, k, mod2);
				s1[val1] = j + 1, s2[val2] = j + 1;
				//cout<<i<<sp<<j<<sp<<k<<sp<<s1[val1]<<" : "<<val1<<sp<<val2<<endl;
			}
		}
	}

	for (int i = m; i >= 1; i--)
	{
		for (int j = 0; j < m - i + 1; j++)
		{
			vector<int> v;
			int val1 = 0, val2 = 0; 
			for (int k = j; k < j + i; k++)
			{
				val1 = add(val1, mul(t[k] - 'a' + 1, e1[k - j], mod1), mod1);
				val2 = add(val2, mul(t[k] - 'a' + 1, e2[k - j], mod2), mod2);
				v.pb(t[k] - 'a' + 1);
			}
			reverse(v.begin(), v.end());
			for (auto k : v)
			{
				val1 = subs(val1, mul(k, e1[i - 1], mod1), mod1);
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, k, mod1);
				val2 = subs(val2, mul(k, e2[i - 1], mod2), mod2);
				val2 = mul(val2, p2, mod2);
				val2 = add(val2, k, mod2);
				//cout<<"--"<<i<<sp<<j<<" : "<<val1<<sp<<val2<<endl;
				if (s1[val1] == s2[val2] && s1[val1] != 0)
				{
					//cout<<"! "<<val1<<sp<<s1[val1]<<endl;
					return {i, {s1[val1] - 1, j}};
				}
			}
		}
	}
	return {0, {0, 0}};
}


int32_t main()
{
	fastio();

	string s, t;
	cin>>s>>t;
	int n = s.size(), m = t.size();

	e1[0] = 1, e2[0] = 1;
	for (int i = 1; i < N; i++)
		e1[i] = mul(e1[i - 1], p1, mod1), e2[i] = mul(e2[i - 1], p2, mod2);

	pair<int, pii> tmp = f(s, t);
	/*
	reverse(s.begin(), s.end());
	pair<int, pii> tmp2 = f(s, t);
	if (tmp.st < tmp2.st)
	{
		//cout<<tmp2.nd.st<<sp<<tmp2.nd.nd<<endl;
		int l = tmp2.st;
		tmp.st = l;
		tmp.nd.st = (n - 1) - tmp2.nd.st - l + 1;	
	}
	*/
	cout<<tmp.st<<endl;
	cout<<tmp.nd.st<<sp<<tmp.nd.nd<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

Compilation message

necklace.cpp: In function 'int32_t main()':
necklace.cpp:105:6: warning: unused variable 'n' [-Wunused-variable]
  105 |  int n = s.size(), m = t.size();
      |      ^
necklace.cpp:105:20: warning: unused variable 'm' [-Wunused-variable]
  105 |  int n = s.size(), m = t.size();
      |                    ^

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 125 ms 13544 KB Output is partially correct
2 Partially correct 84 ms 12256 KB Output is partially correct
3 Partially correct 98 ms 10436 KB Output is partially correct
4 Partially correct 228 ms 20556 KB Output is partially correct
5 Correct 519 ms 40056 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 125 ms 13544 KB Output is partially correct
2 Partially correct 84 ms 12256 KB Output is partially correct
3 Partially correct 98 ms 10436 KB Output is partially correct
4 Partially correct 228 ms 20556 KB Output is partially correct
5 Correct 519 ms 40056 KB Output is correct
6 Execution timed out 1574 ms 86220 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 125 ms 13544 KB Output is partially correct
2 Partially correct 84 ms 12256 KB Output is partially correct
3 Partially correct 98 ms 10436 KB Output is partially correct
4 Partially correct 228 ms 20556 KB Output is partially correct
5 Correct 519 ms 40056 KB Output is correct
6 Execution timed out 1574 ms 86220 KB Time limit exceeded
7 Halted 0 ms 0 KB -