oj.uz

답안 #646426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646426 2022-09-29T18:49:26 Z dozer Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 149992 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];

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

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

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

pair<int, pii> f(string s, string t)
{
	unordered_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;
		tmp.nd.nd = tmp2.nd.nd;	
	}
	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:20: warning: unused variable 'm' [-Wunused-variable]
  105 |  int n = s.size(), m = t.size();
      |                    ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 11660 KB Output is correct
2 Correct 68 ms 9132 KB Output is correct
3 Correct 58 ms 8092 KB Output is correct
4 Correct 154 ms 15264 KB Output is correct
5 Correct 445 ms 30404 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 11660 KB Output is correct
2 Correct 68 ms 9132 KB Output is correct
3 Correct 58 ms 8092 KB Output is correct
4 Correct 154 ms 15264 KB Output is correct
5 Correct 445 ms 30404 KB Output is correct
6 Execution timed out 1595 ms 149992 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 11660 KB Output is correct
2 Correct 68 ms 9132 KB Output is correct
3 Correct 58 ms 8092 KB Output is correct
4 Correct 154 ms 15264 KB Output is correct
5 Correct 445 ms 30404 KB Output is correct
6 Execution timed out 1595 ms 149992 KB Time limit exceeded
7 Halted 0 ms 0 KB -