Submission #873164

# Submission time Handle Problem Language Result Execution time Memory
873164 2023-11-14T14:53:06 Z vjudge1 Necklace (Subtask 4) (BOI19_necklace4) C++14
0 / 15
81 ms 2672 KB
#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
  os << '(' << p.first << ',' << p.second << ')';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
  os << '{';
  bool osu = 1;
  for(auto &i : v) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const deque<T> &v) {
  os << '{';
  bool osu = 1;
  for(auto &i : v) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}
template<class T,long long unsigned int size>
ostream& operator<<(ostream& os, const array<T,size> &arr) {
  os << '{';
  bool osu = 1;
  for(auto &i : arr) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}

#define ll long long
#define ull unsigned long long
#define lll __int128
#define rep(i,n,N) for(int i=(n);i<=(N);++i)
#define For(i,n,N) for(int i=(n);i< (N);++i)
#define rap(i,n,N) for(int i=(n);i>=(N);--i)
#define rip(i,n,N,V) for(int i=(n);i<=(N);i+=V)
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
//#define le left
//#define ri right
#define fi first
#define se second
//#define ff fi.fi
//#define fs fi.se
//#define sf se.fi
//#define ss se.se
#define lc (id<<1)
#define rc ((id<<1)|1)
#define debug(x) cout << #x << " -> " << (x) << endl
#define out(x,y) cout << ">> " << (x) << " " << (y) << endl
#define ou3(x,y,z) cout << ">> " << (x) << " " << (y) << " " << (z) << endl
#define mems(x,y) memset(&x,y,sizeof x)
#define memsv(x,y) memset(&x[0], y, sizeof(x[0]) * x.size())
#define popcount __builtin_popcountll
#define clz(x) (1<<(31-__builtin_clz(x)))
#define clzll(x) (1LL<<(63-__builtin_clzll(x)))
#define all(x) x.begin(),x.end()
#define rsort(x) sort(x), reverse(x)
#define revsort(a,b) sort(a,b), reverse(a,b)
#define PQ(T) priority_queue<T>
#define PQr(T) priority_queue<T, vector<T>, greater<T>>
#define permute(x) while(next_permutation(all(x)))
#define distinct(x) x.erase(unique(all(x)),x.end())
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pii>
#define vll vector<ll>
#define vlll vector<pll>
#define vvll vector<vll>
#define ari(x) array<int,x>
#define arll(x) array<ll,x>
#define ard(x) array<double,x>
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define pllll pair<pll,pll>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define psi pair<string,int>
#define endl '\n'
const int MAX = 3e3+5;
const ll MOD = 2078628313;
const ll MOD2 = 2010405347;
const ll INF = 2e18;
const int dr[]={1,-1,0,0,1,1,-1,-1};
const int dc[]={0,0,-1,1,1,-1,1,-1};
const double pi = acos(-1);
const double EPS = 1e-9;
const int block = 2e3;
inline ll pw(ll x,ll y,ll md=MOD){ll ret=1;x%=md;while(y){if(y&1)ret=ret*x%md;x=x*x%md,y>>=1;}return ret;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int K = 26;
int cv[K][K][K][K];
int n,m;
ll xx[MAX],yy[MAX],x[MAX],y[MAX],hs[MAX],key = 724729;
map<ll,int> z;
map<int,int> g;
string s,t;

ari(3) solve(){
	rep(i,1,n)x[i] = (x[i-1]*key + s[i-1] + 69) % MOD;
	rep(i,1,m)y[i] = (y[i-1]*key + t[i-1] + 69) % MOD;
	rep(i,4,n)xx[i] = xx[i-1] + cv[s[i-4]][s[i-3]][s[i-2]][s[i-1]];
	rep(i,4,m)yy[i] = yy[i-1] + cv[t[i-4]][t[i-3]][t[i-2]][t[i-1]];
	int le,ri,mid,res,val;
	bool st;
	int a,b;
	le = 1, ri = min(n,m);
	while(le<=ri){
		mid = le+ri>>1;
		g.clear();
		rep(i,mid,n)g[(x[i]+x[i-mid]*hs[mid])%MOD] = i;
		st = 0;
		rep(i,mid,m){
			val = (y[i]+y[i-mid]*hs[mid])%MOD;
			if(g.count(val)){
				a = g[val]-mid, b = i-mid;
				st = 1;
				break;
			}
		}
		if(st)res = mid, le = mid+1;
		else ri = mid-1;
	}
	if(res==1)return {res, a, b};
	int l1, l2;
	l1 = res+1, l2 = min({n,m,res*2});
	ll v;
	rap(k,l2,l1){
		z.clear();
		if(k==3){
			rep(i,k,n){
				v = (ll)cv[s[i-3]][s[i-2]][s[i-1]][0]+
					cv[s[i-2]][s[i-1]][s[i-3]][0]+
					cv[s[i-1]][s[i-3]][s[i-2]][0];
				z[v] = i;
			}
			rep(i,k,m){
				v = (ll)cv[t[i-3]][t[i-2]][t[i-1]][0]+
					cv[t[i-2]][t[i-1]][t[i-3]][0]+
					cv[t[i-1]][t[i-3]][t[i-2]][0];
				if(z.count(v))return {k, z[v]-k, i-k};
			}
		}
		else {
			rep(i,k,n){
				v = xx[i]-xx[i-k+3]+cv[s[i-3]][s[i-2]][s[i-1]][s[i-k]]+
									cv[s[i-2]][s[i-1]][s[i-k]][s[i-k+1]]+
									cv[s[i-1]][s[i-k]][s[i-k+1]][s[i-k+2]];
				z[v] = i;
			}
			rep(i,k,m){
				v = yy[i]-yy[i-k+3]+cv[t[i-3]][t[i-2]][t[i-1]][t[i-k]]+
									cv[t[i-2]][t[i-1]][t[i-k]][t[i-k+1]]+
									cv[t[i-1]][t[i-k]][t[i-k+1]][t[i-k+2]];
				if(z.count(v))return {k, z[v]-k, i-k};
			}
		}
	}
	return {res, a, b};
}

int main(){
//	cout<<fixed<<setprecision(10);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	For(a,0,K)For(b,0,K)For(c,0,K)For(d,0,K)cv[a][b][c][d] = rng()%MOD;
	cin>>s>>t;
	n = s.size();
	m = t.size();
	for(auto &i:s)i-= 'a';
	for(auto &i:t)i-= 'a';
	int o = max(n,m);
	hs[0] = MOD-1;
	rep(i,1,o)hs[i] = hs[i-1]*key % MOD;
	ari(3) ans = solve(), tmp;
	reverse(all(t));
	tmp = solve();
	if(tmp[0]>ans[0]){
		ans = tmp;
		ans[2] = m-(ans[2]+ans[0]);
	}
	cout<<ans[0]<<endl;
	cout<<ans[1]<<" "<<ans[2]<<endl;
	return 0;
}

Compilation message

necklace.cpp: In function 'std::array<int, 3> solve()':
necklace.cpp:114:39: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |  rep(i,4,n)xx[i] = xx[i-1] + cv[s[i-4]][s[i-3]][s[i-2]][s[i-1]];
      |                                       ^
necklace.cpp:114:47: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |  rep(i,4,n)xx[i] = xx[i-1] + cv[s[i-4]][s[i-3]][s[i-2]][s[i-1]];
      |                                               ^
necklace.cpp:114:55: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |  rep(i,4,n)xx[i] = xx[i-1] + cv[s[i-4]][s[i-3]][s[i-2]][s[i-1]];
      |                                                       ^
necklace.cpp:114:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |  rep(i,4,n)xx[i] = xx[i-1] + cv[s[i-4]][s[i-3]][s[i-2]][s[i-1]];
      |                                                               ^
necklace.cpp:115:39: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |  rep(i,4,m)yy[i] = yy[i-1] + cv[t[i-4]][t[i-3]][t[i-2]][t[i-1]];
      |                                       ^
necklace.cpp:115:47: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |  rep(i,4,m)yy[i] = yy[i-1] + cv[t[i-4]][t[i-3]][t[i-2]][t[i-1]];
      |                                               ^
necklace.cpp:115:55: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |  rep(i,4,m)yy[i] = yy[i-1] + cv[t[i-4]][t[i-3]][t[i-2]][t[i-1]];
      |                                                       ^
necklace.cpp:115:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |  rep(i,4,m)yy[i] = yy[i-1] + cv[t[i-4]][t[i-3]][t[i-2]][t[i-1]];
      |                                                               ^
necklace.cpp:121:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |   mid = le+ri>>1;
      |         ~~^~~
necklace.cpp:144:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  144 |     v = (ll)cv[s[i-3]][s[i-2]][s[i-1]][0]+
      |                      ^
necklace.cpp:144:30: warning: array subscript has type 'char' [-Wchar-subscripts]
  144 |     v = (ll)cv[s[i-3]][s[i-2]][s[i-1]][0]+
      |                              ^
necklace.cpp:144:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  144 |     v = (ll)cv[s[i-3]][s[i-2]][s[i-1]][0]+
      |                                      ^
necklace.cpp:145:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |      cv[s[i-2]][s[i-1]][s[i-3]][0]+
      |               ^
necklace.cpp:145:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |      cv[s[i-2]][s[i-1]][s[i-3]][0]+
      |                       ^
necklace.cpp:145:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |      cv[s[i-2]][s[i-1]][s[i-3]][0]+
      |                               ^
necklace.cpp:146:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |      cv[s[i-1]][s[i-3]][s[i-2]][0];
      |               ^
necklace.cpp:146:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |      cv[s[i-1]][s[i-3]][s[i-2]][0];
      |                       ^
necklace.cpp:146:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |      cv[s[i-1]][s[i-3]][s[i-2]][0];
      |                               ^
necklace.cpp:150:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  150 |     v = (ll)cv[t[i-3]][t[i-2]][t[i-1]][0]+
      |                      ^
necklace.cpp:150:30: warning: array subscript has type 'char' [-Wchar-subscripts]
  150 |     v = (ll)cv[t[i-3]][t[i-2]][t[i-1]][0]+
      |                              ^
necklace.cpp:150:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  150 |     v = (ll)cv[t[i-3]][t[i-2]][t[i-1]][0]+
      |                                      ^
necklace.cpp:151:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  151 |      cv[t[i-2]][t[i-1]][t[i-3]][0]+
      |               ^
necklace.cpp:151:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  151 |      cv[t[i-2]][t[i-1]][t[i-3]][0]+
      |                       ^
necklace.cpp:151:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  151 |      cv[t[i-2]][t[i-1]][t[i-3]][0]+
      |                               ^
necklace.cpp:152:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  152 |      cv[t[i-1]][t[i-3]][t[i-2]][0];
      |               ^
necklace.cpp:152:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  152 |      cv[t[i-1]][t[i-3]][t[i-2]][0];
      |                       ^
necklace.cpp:152:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  152 |      cv[t[i-1]][t[i-3]][t[i-2]][0];
      |                               ^
necklace.cpp:158:34: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |     v = xx[i]-xx[i-k+3]+cv[s[i-3]][s[i-2]][s[i-1]][s[i-k]]+
      |                                  ^
necklace.cpp:158:42: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |     v = xx[i]-xx[i-k+3]+cv[s[i-3]][s[i-2]][s[i-1]][s[i-k]]+
      |                                          ^
necklace.cpp:158:50: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |     v = xx[i]-xx[i-k+3]+cv[s[i-3]][s[i-2]][s[i-1]][s[i-k]]+
      |                                                  ^
necklace.cpp:158:58: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |     v = xx[i]-xx[i-k+3]+cv[s[i-3]][s[i-2]][s[i-1]][s[i-k]]+
      |                                                          ^
necklace.cpp:159:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  159 |          cv[s[i-2]][s[i-1]][s[i-k]][s[i-k+1]]+
      |                   ^
necklace.cpp:159:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  159 |          cv[s[i-2]][s[i-1]][s[i-k]][s[i-k+1]]+
      |                           ^
necklace.cpp:159:35: warning: array subscript has type 'char' [-Wchar-subscripts]
  159 |          cv[s[i-2]][s[i-1]][s[i-k]][s[i-k+1]]+
      |                                   ^
necklace.cpp:159:45: warning: array subscript has type 'char' [-Wchar-subscripts]
  159 |          cv[s[i-2]][s[i-1]][s[i-k]][s[i-k+1]]+
      |                                             ^
necklace.cpp:160:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |          cv[s[i-1]][s[i-k]][s[i-k+1]][s[i-k+2]];
      |                   ^
necklace.cpp:160:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |          cv[s[i-1]][s[i-k]][s[i-k+1]][s[i-k+2]];
      |                           ^
necklace.cpp:160:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |          cv[s[i-1]][s[i-k]][s[i-k+1]][s[i-k+2]];
      |                                     ^
necklace.cpp:160:47: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |          cv[s[i-1]][s[i-k]][s[i-k+1]][s[i-k+2]];
      |                                               ^
necklace.cpp:164:34: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |     v = yy[i]-yy[i-k+3]+cv[t[i-3]][t[i-2]][t[i-1]][t[i-k]]+
      |                                  ^
necklace.cpp:164:42: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |     v = yy[i]-yy[i-k+3]+cv[t[i-3]][t[i-2]][t[i-1]][t[i-k]]+
      |                                          ^
necklace.cpp:164:50: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |     v = yy[i]-yy[i-k+3]+cv[t[i-3]][t[i-2]][t[i-1]][t[i-k]]+
      |                                                  ^
necklace.cpp:164:58: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |     v = yy[i]-yy[i-k+3]+cv[t[i-3]][t[i-2]][t[i-1]][t[i-k]]+
      |                                                          ^
necklace.cpp:165:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  165 |          cv[t[i-2]][t[i-1]][t[i-k]][t[i-k+1]]+
      |                   ^
necklace.cpp:165:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  165 |          cv[t[i-2]][t[i-1]][t[i-k]][t[i-k+1]]+
      |                           ^
necklace.cpp:165:35: warning: array subscript has type 'char' [-Wchar-subscripts]
  165 |          cv[t[i-2]][t[i-1]][t[i-k]][t[i-k+1]]+
      |                                   ^
necklace.cpp:165:45: warning: array subscript has type 'char' [-Wchar-subscripts]
  165 |          cv[t[i-2]][t[i-1]][t[i-k]][t[i-k+1]]+
      |                                             ^
necklace.cpp:166:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |          cv[t[i-1]][t[i-k]][t[i-k+1]][t[i-k+2]];
      |                   ^
necklace.cpp:166:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |          cv[t[i-1]][t[i-k]][t[i-k+1]][t[i-k+2]];
      |                           ^
necklace.cpp:166:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |          cv[t[i-1]][t[i-k]][t[i-k+1]][t[i-k+2]];
      |                                     ^
necklace.cpp:166:47: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |          cv[t[i-1]][t[i-k]][t[i-k+1]][t[i-k+2]];
      |                                               ^
necklace.cpp:171:19: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  171 |  return {res, a, b};
      |                   ^
necklace.cpp:118:6: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |  int a,b;
      |      ^
# Verdict Execution time Memory Grader output
1 Correct 24 ms 2396 KB Output is correct
2 Correct 18 ms 2396 KB Output is correct
3 Correct 48 ms 2392 KB Output is correct
4 Correct 52 ms 2392 KB Output is correct
5 Correct 81 ms 2652 KB Output is correct
6 Incorrect 49 ms 2672 KB Output isn't correct
7 Halted 0 ms 0 KB -