oj.uz

답안 #156350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156350 2019-10-05T09:48:06 Z ryansee Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 1275 ms 504 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (3006)
string A[2];
const ll mod=1e9+9;
const ll base=37;
ll pw[MAXN];
ll s[2], ans=0, l[2], r[2], n[2]; bool rev;
void solve() {
	auto start = chrono::high_resolution_clock::now();
	while(1) {
		auto finish=chrono::high_resolution_clock::now();
		chrono::duration<ld> elapsed=finish-start;
		if(elapsed.count() > (ld)0.65) break;
		FOR(i,0,1) {
			l[i]=rand(0, n[i]-1);
			r[i]=l[i];
		}
		if(A[0][l[0]]!=A[1][l[1]] || 2*(min(l[0],l[1])+min(n[0]-r[0]-1, n[1]-r[1]-1)) <= ans) continue;
		while(min(l[0],l[1]) > 0 && A[0][l[0]-1]==A[1][l[1]-1]) --l[0], --l[1];
		while(r[0]+1 < n[0] && r[1]+1 < n[1] && A[0][r[0]+1]==A[1][r[1]+1]) ++r[0], ++r[1];
		ll len=r[0]-l[0]+1;
		if(2*len <= ans) continue;
		if(len > ans) {
			ans=len;
			tie(s[0],s[1])=tie(l[0],l[1]);
			if(rev) s[1]=n[1]-r[1]-1;
		}
		FOR(i,0,1) {
			vector<ll> hash(2, 0);
			FOR(j,1,len) {
				if(r[i] + j >= n[i] || l[!i] - j < 0) break;
				hash[i]+=(ll)(A[i][r[i]+j]-'a')*pw[j-1]%mod;
				hash[i]%=mod;
				hash[!i]*=base, hash[!i]%=mod;
				hash[!i]+=(ll)(A[!i][l[!i]-j]-'a'), hash[!i]%=mod;
				if(hash[i] == hash[!i] && len+j > ans){
					ans=len+j;
					s[0]=l[i];
					s[1]=l[!i]-j;
					if(i) swap(s[0],s[1]);
					if(rev) s[1]=n[1]-r[1]-(i?j:0)-1;
					// if(s[1] == 6 && rev) cerr<<n[1]<<' '<<l[1]<<' '<<r[1]<<' '<<i<<' '<<j<<'\n';
				}
			}
		}
	}
}
int main()
{
	FAST
	cin>>A[0]>>A[1];
	n[0]=A[0].size(), n[1]=A[1].size();
	pw[0]=1; FOR(i,1,MAXN-1) pw[i]=pw[i-1]*base%mod;
	solve();
	reverse(all(A[1]));rev=1;
	solve();
	assert(ans), cout<<ans<<'\n'<<s[0]<<' '<<s[1]<<'\n';
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1241 ms 420 KB Output is correct
2 Correct 1248 ms 424 KB Output is correct
3 Correct 1264 ms 428 KB Output is correct
4 Correct 1267 ms 376 KB Output is correct
5 Correct 1270 ms 504 KB Output is correct
6 Correct 1255 ms 424 KB Output is correct
7 Correct 1275 ms 376 KB Output is correct
8 Correct 1271 ms 376 KB Output is correct
9 Correct 1267 ms 420 KB Output is correct