Submission #943118

#	Time	Username	Problem	Language	Result	Execution time	Memory
943118		phoenix0423	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	1 ms	348 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e18;
const int maxn = 1e5 + 5;
const int N = 1e9 + 7;
const int A = 923482345;
int p[maxn];
map<int, int> mp;
pll ans = {0, 0};

int smallest_cyclic_shift(string s){
	s = s + s;
	int n = s.size();
	vector<int> st;
	int i = 0;
	while(i < n){
		int j = i + 1, k = i;
		while(j < n && s[k] <= s[j]){
			if(s[k] < s[j]) k = i;
			else k++;
			j++;
		}
		while(i <= k){
			st.pb(i);
			i += j - k;
		}
	}
	for(int i = 0; i < st.size(); i++){
		if(i == st.size() - 1 || (st[i] < n / 2 && st[i + 1] >= n / 2)){
			return st[i];
		}
	}
	return 0;
}
int hashs(string s, int id){
	string nw = s.substr(id) + s.substr(0, id);
	int ret = 0;
	for(int i = 0; i < s.size(); i++) (ret += p[i] * nw[i]) %= N;
	// cout<<"hash : "<<nw<<" "<<ret<<"\n";
	return ret;
}
signed main(void){
	fastio;
	string s, t;
	cin>>s>>t;
	int n = max(s.size(), t.size());
	p[0] = 1;
	for(int i = 1; i < n; i++) p[i] = p[i - 1] * A % N;
	int l = 0, r = n + 1;
	while(l + 1 < r){
		mp.clear();
		int m = (l + r) / 2;
		for(int i = 0; i + m - 1 < s.size(); i++){
			string nw = "";
			for(int j = 0; j < m; j++) nw += s[i + j];
			int id = smallest_cyclic_shift(nw);
			// cout<<nw<<" "<<id<<"\n";
			// cout<<"put : "<<hashs(nw, id)<<"\n";
			mp[hashs(nw, id)] = i + 1;
			reverse(nw.begin(), nw.end());
			id = smallest_cyclic_shift(nw);
			mp[hashs(nw, id)] = i + 1;
		}
		int ok = 0;
		for(int i = 0; i + m - 1 < t.size(); i++){
			string nw = "";
			for(int j = 0; j < m; j++) nw += t[i + j];
			int id = smallest_cyclic_shift(nw);
			if(mp.find(hashs(nw, id)) != mp.end()){
				ans = {mp[hashs(nw, id)], i + 1};
				ok = 1;
				break;
			}
			reverse(nw.begin(), nw.end());
			id = smallest_cyclic_shift(nw);
			// cout<<"search : "<<hashs(nw, id)<<"\n";
			if(mp.find(hashs(nw, id)) != mp.end()){
				ans = {mp[hashs(nw, id)], i + 1};
				ok = 1;
				break;
			}
		}
		if(ok) l = m;
		else r = m;
	}
	cout<<l<<"\n";
	cout<<ans.f<<" "<<ans.s<<"\n";
}

Compilation message (stderr)

necklace.cpp: In function 'long long int smallest_cyclic_shift(std::string)':
necklace.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i = 0; i < st.size(); i++){
      |                 ~~^~~~~~~~~~~
necklace.cpp:39:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(i == st.size() - 1 || (st[i] < n / 2 && st[i + 1] >= n / 2)){
      |      ~~^~~~~~~~~~~~~~~~
necklace.cpp: In function 'long long int hashs(std::string, long long int)':
necklace.cpp:48:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0; i < s.size(); i++) (ret += p[i] * nw[i]) %= N;
      |                 ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:63:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i + m - 1 < s.size(); i++){
      |                  ~~~~~~~~~~^~~~~~~~~~
necklace.cpp:75:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i + m - 1 < t.size(); i++){
      |                  ~~~~~~~~~~^~~~~~~~~~

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