PSTU_Optimist

Barisal | How Does Climate Change Affect You?

Team Updates

In the year 2059, Rover "Delta 32" returned to the earth surface with some great news having plant sample which was planted on the Mars greenhouse project.

Rover data also shows that they have been producing enough oxygen for 50 humans for about a year. That result leads the scientists to go on mars for further research.

In the meantime, ww3 has begun. Almost 99% of the population has died in war. Scientists suggest going on mars with few people alive in that war. They put civilians in cryo chambers for using low oxygen until they reach mars.

After reaching mars, scientists begin to produce more greenhouses for oxygen and food. They train humans to cope with the situations. After training sessions, scientists let them work with scientists to survive on mars as earth is long gone by then.

FazleRabbe Bipul

	#include<bits/stdc++.h>
	#include<ext/pb_ds/assoc_container.hpp>//required
	#include<ext/pb_ds/tree_policy.hpp>//required
	usingnamespace__gnu_pbds;//
	usingnamespacestd;
	#definelllonglong
	#definepb push_back
	#defineff first
	#definess second
	#definepii pair<int, int>
	#definepll pair<longlongint, longlongint>
	#defineALL(s) (s).begin(), (s).end()
	#definerALL(s) (s).rbegin(), (s).rend()
	#defineshow(x) cout << #x << " : " << x << endl
	#definefastios_base::sync_with_stdio(false);cin.tie(NULL)
	template<classT>
	using indexed_set = tree<T,null_type,less<T>,rb_tree_tag,
	tree_order_statistics_node_update>;//indexed_set<ll> st;st.order_of_key(x);
	constlonglong mod = 1000000007;


	vector<int> constructTempArray(string pattern) {
	vector<int> lps(pattern.length());
	int index = 0;
	for (int i = 1; i < (int) pattern.length(); ) {
	if (pattern[i] == pattern[index]) lps[i] = index + 1, ++index, ++i;
	else {
	if (index != 0) index = lps[index - 1];
	else lps[i] = index, ++i;
	}
	}
	return lps;
	}

	voidKMPMultipleTimes (string text, string pattern, vector<int>&paichi) {
	bool found = false;
	vector<int> lps = constructTempArray(pattern);
	int j = 0, i = 0;

	// i --> text, j --> pattern
	while (i < (int) text.length()) {
	if (text[i] == pattern[j]) ++i, ++j;
	else {
	if (j != 0) j = lps[j - 1];
	else ++i;
	}

	if (j == (int) pattern.length()) {
	paichi[i-pattern.size()]=1;
	j = lps[j-1];
	found = true;
	}
	}
	}

	vector<int> sort_cyclic_shifts(string const& s) {
	int n = s.size();
	constint alphabet = 256;

	vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
	for (int i = 0; i < n; i++)
	cnt[s[i]]++;
	for (int i = 1; i < alphabet; i++)
	cnt[i] += cnt[i-1];
	for (int i = 0; i < n; i++)
	p[--cnt[s[i]]] = i;
	c[p[0]] = 0;
	int classes = 1;
	for (int i = 1; i < n; i++) {
	if (s[p[i]] != s[p[i-1]])
	classes++;
	c[p[i]] = classes - 1;
	}
	vector<int> pn(n), cn(n);
	for (int h = 0; (1 << h) < n; ++h) {
	for (int i = 0; i < n; i++) {
	pn[i] = p[i] - (1 << h);
	if (pn[i] < 0)
	pn[i] += n;
	}
	fill(cnt.begin(), cnt.begin() + classes, 0);
	for (int i = 0; i < n; i++)
	cnt[c[pn[i]]]++;
	for (int i = 1; i < classes; i++)
	cnt[i] += cnt[i-1];
	for (int i = n-1; i >= 0; i--)
	p[--cnt[c[pn[i]]]] = pn[i];
	cn[p[0]] = 0;
	classes = 1;
	for (int i = 1; i < n; i++) {
	pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
	pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
	if (cur != prev)
	++classes;
	cn[p[i]] = classes - 1;
	}
	c.swap(cn);
	}
	return p;
	}

	vector<int> lcp_construction(string const& s, vector<int> const& p) {
	int n = s.size();
	vector<int> rank(n, 0);
	for (int i = 0; i < n; i++)
	rank[p[i]] = i;

	int k = 0;
	vector<int> lcp(n-1, 0);
	for (int i = 0; i < n; i++) {
	if (rank[i] == n - 1) {
	k = 0;
	continue;
	}
	int j = p[rank[i] + 1];
	while (i + k < n && j + k < n && s[i+k] == s[j+k])
	k++;
	lcp[rank[i]] = k;
	if (k)
	k--;
	}
	return lcp;
	}


	intmain()
	{
	int ts;
	cin >> ts;
	for(int cs=1; cs<=ts; cs++){

	string s, b;
	cin >> s >> b;
	ll n=s.size();

	vector<int>paichi(n,0), cum(n,0);
	KMPMultipleTimes(s, b, paichi);
	cum[0]=paichi[0];
	for(int i=1; i<n; i++) cum[i] = cum[i-1] + paichi[i];
	//for(auto it: cum) cout << it << " ";
	// cout << endl;
	s+="$";


	vector<int>sa=sort_cyclic_shifts(s);
	vector<int>lcp=lcp_construction(s, sa);
	sa.erase(sa.begin());


	ll ans = 0, ls=n;
	vector<ll>last(n, -1);
	for(int i=n-1; i>=0; i--){
	if(paichi[i]==1)ls=i;
	last[i]=ls;
	}
	for(int i=0; i<n; i++) cout << paichi[i] << "";
	cout << endl;
	for(int i=0; i<n; i++) cout << last[i] << "";
	cout << endl;
	ll m=b.size();
	for(ll i=0; i<n; i++){
	if(last[i] <= lcp[i]+sa[i])continue;
	ans += min(n,(last[i]+m-1))-sa[i];
	}

	cout <<"Case "<<cs << ": "<< ans << endl;


	}
	}

view raw Code.cpp hosted with ❤ by GitHub

FazleRabbe Bipul