FBHC17 R3 Solution

fb17r3a.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int rev[1005], sfx[1005];
char str[1005];
int n;

void solve(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&rev[i]);
		rev[i]--;
		sfx[rev[i]] = i;
	}
	memset(str, 0, sizeof(str));
	rev[n] = -1;
	str[sfx[0]] = 'A';
	for(int i=1; i<n; i++){
		int p1 = sfx[i-1] + 1;
		int p2 = sfx[i] + 1;
		if(rev[p1] < rev[p2]){
			str[sfx[i]] = str[sfx[i-1]];
		}
		else{
			str[sfx[i]] = str[sfx[i-1]] + 1;
			if(str[sfx[i]] > 'Z'){
				puts("-1");
				return;
			}
		}
	}
	cout << str << endl;
	int arr[1005];
	for(int i=0; i<n; i++) arr[i] = i;
	sort(arr, arr + n, [&](const int &a, const int &b){
		if(a == b) return false;
		for(int i=0; i<=n; i++){
			if(str[a+i] != str[b+i]){
				return str[a+i] < str[b+i];
			}
		}
	});
	for(int i=0; i<n; i++){
		assert(arr[i] == sfx[i]);
	}
}

int main(){
	int t;
	scanf("%d",&t);
	for(int i=1; i<=t; i++){
		printf("Case #%d: ", i);
		solve();
	}
}

fb17r3b.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint fact[4000005], invf[4000005];

lint bino(int x, int y){
	return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}

int n, a[2000005], b[2000005];
int chk1[2000005], chk2[2000005];
int hl[2000005], hr[2000005];

vector<pi> v;

int solve(int s, int e, int *a){
	if((e - s + 1) % 2 != 0) return -1;
	int cnt = 0;
	for(int i=s; i<=e; i+=2){
		if(a[i] != a[i+1]){
			if(i + 3 <= e && a[i] == a[i+2] && a[i+1] == a[i+3]){
				cnt++;
				i += 2;
				continue;
			}
			else return -1;
		}
		cnt++;
	}
	return cnt;
}

lint solve(int sx, int ex, int sy, int ey){
	while(chk1[sx] && sx <= ex) sx++;
	while(chk1[ex] && sx <= ex) ex--;
	while(chk2[sy] && sy <= ey) sy++;
	while(chk2[ey] && sy <= ey) ey--;
	int p1 = solve(sx, ex, a);
	int p2 = solve(sy, ey, b);
	if(p1 == -1 || p2 == -1) return 0;
	return bino(p1 + p2, p2);
}

void solve(){
	if(n == 1){
		puts("1");
		return;
	}
	for(int i=1; i<=n; i++){
		hl[a[i]] = i;
		hr[b[i]] = i;
	}
	for(int i=1; i<=n; i++){
		if(hl[i] && hr[i]){
			v.push_back(pi(hl[i], hr[i]));
		}
	}
	sort(v.begin(), v.end());
	lint ret = 1;
	for(int i=1; i<v.size(); i++){
		if(v[i-1].second > v[i].second){
			if(v[i].first == v[i-1].first + 1 && v[i-1].second == v[i].second + 1){
				swap(v[i].second, v[i-1].second);
				ret *= 2;
				ret %= mod;
				continue;
			}
			puts("0");
			return;
		}
	}
	for(int i=0; i<v.size(); i++){
		int l = 0, r = 0;
		int p1 = v[i].first, p2 = v[i].second;
		if(p1 < n && p1 > 1 && a[p1-1] == a[p1+1]) l = 1;
		if(p2 < n && p2 > 1 && b[p2-1] == b[p2+1]) r = 1;
		if(l && r){
			puts("0");
			return;
		}
		if(l) chk1[p1-1] = chk1[p1+1] = 1;
		if(r) chk2[p2-1] = chk2[p2+1] = 1;
		if(l || r) ret = (ret * 2) % mod;
	}
	if(v.empty()){
		ret *= solve(1, n, 1, n);
		ret %= mod;
	}
	else{
		ret *= solve(1, v[0].first - 1, 1, v[0].second - 1);
		ret %= mod;
		ret *= solve(v.back().first + 1, n, v.back().second + 1, n);
		ret %= mod;
		for(int i=1; i<v.size(); i++){
			ret *= solve(v[i-1].first + 1, v[i].first - 1, v[i-1].second + 1, v[i].second - 1);
			ret %= mod;
		}
	}
	printf("%lld\n", ret);
}

int tmp[2000005];

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}


void input(){
	v.clear();
	memset(hl, 0, sizeof(hl));
	memset(hr, 0, sizeof(hr));
	memset(chk1, 0, sizeof(chk1));
	memset(chk2, 0, sizeof(chk2));
	cin >> n;
	int ka, kb;
	cin >> a[1] >> ka;
	int p = 2;
	for(int i=0; i<ka; i++){
		int r, t;
		scanf("%d %d",&r, &t);
		for(int j=0; j<t; j++){
			scanf("%d",&tmp[p]);
			for(int k=1; k<r; k++){
				tmp[p + k * t] = tmp[p + k * t - t];
			}
			p++;
		}
		p += r * t - t;
	}
	for(int i=2; i<=n; i++){
		a[i] = a[i-1] + tmp[i];
	}
	cin >> b[1] >> ka;
	p = 2;
	for(int i=0; i<ka; i++){
		int r, t;
		scanf("%d %d",&r, &t);
		for(int j=0; j<t; j++){
			scanf("%d",&tmp[p]);
			for(int k=1; k<r; k++){
				tmp[p + k * t] = tmp[p + k * t - t];
			}
			p++;
		}
		p += r * t - t;
	}
	for(int i=2; i<=n; i++){
		b[i] = b[i-1] + tmp[i];
	}
}

int main(){
	fact[0] = invf[0] = 1;
	for(int i=1; i<=4000000; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod-2);
	}
	int t;
	scanf("%d",&t);
	for(int i=1; i<=t; i++){
		printf("Case #%d: ", i);
		input();
		solve();
	}
}

fb17r3c.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;

void dijkstra();

int n;
lint a[2000005], b[2000005], l;
int c[1000005];

struct bit{
	int tree[1000005];
	void clear(){
		memset(tree, 0, sizeof(tree));
	}
	void add(int x, lint v){
		v %= mod;
		v += mod;
		v %= mod;
		x++;
		while(x <= n){
			tree[x] += v;
			tree[x] %= mod;
			x += x & -x;
		}
	}
	int query(int x){
		x++;
		int ret = 0;
		while(x){
			ret += tree[x];
			ret %= mod;
			x -= x & -x;
		}
		return ret;
	}
	int query(int s, int e){
		return (query(e) - query(s-1) + mod) % mod;
	}
}cnt1, sum1, sum2, cnt2, sum3, sum4;

int op1[1000005], op2[1000005];

void solve(){
	dijkstra();
	lint ret = 0;
	for(int i=1; i<=n; i++){
		ret += b[i];
		ret %= mod;
	}
	for(int i=1; i<=n; i++){
		l += a[i];
		a[i] += a[i-1];
	}
	for(int i=n; i; i--){
		a[i] = a[i-1];
	}
	vector<lint> fac1, fac2;
	for(int i=1; i<=n; i++){
		fac1.push_back(a[i] - b[i]);
		fac2.push_back(l - a[i] - b[i]);
	}
	sort(fac1.begin(), fac1.end());
	sort(fac2.begin(), fac2.end());
	fac1.resize(unique(fac1.begin(), fac1.end()) - fac1.begin());
	fac2.resize(unique(fac2.begin(), fac2.end()) - fac2.begin());
	for(int i=1; i<=n; i++){
		op1[i] = lower_bound(fac1.begin(), fac1.end(), a[i] - b[i]) - fac1.begin();
		op2[i] = lower_bound(fac2.begin(), fac2.end(), l - a[i] - b[i]) - fac2.begin();
	}
	cnt1.clear();
	sum1.clear();
	sum2.clear();
	cnt2.clear();
	sum3.clear();
	sum4.clear();
	int e = 1;
	for(int i=1; i<=n; i++){
		cnt2.add(op2[i], 1);
		sum3.add(op2[i], b[i]);
		sum4.add(op2[i], (l - a[i]) % mod);
	}
	for(int i=1; i<=n; i++){
		while(e <= n && a[e] - a[i] < l - a[e] + a[i]){
			cnt1.add(op1[e], 1);
			sum1.add(op1[e], b[e]);
			sum2.add(op1[e], a[e] % mod);
			cnt2.add(op2[e], mod-1);
			sum3.add(op2[e], mod-b[e]);
			sum4.add(op2[e], mod - (l - a[e]) % mod);
			e++;
		}
		cnt1.add(op1[i], mod-1);
		sum1.add(op1[i], mod-b[i]);
		sum2.add(op1[i], mod-a[i] % mod);
		int k1 = lower_bound(fac1.begin(), fac1.end(), b[i] + a[i] + 1) - fac1.begin();
		ret += 1ll * b[i] * cnt1.query(k1, n-1) % mod + sum1.query(k1, n-1);
		ret %= mod;
		ret += sum2.query(0, k1-1) - 1ll * (a[i] % mod) * cnt1.query(0, k1-1) % mod + mod;
		ret %= mod;
		int k2 = lower_bound(fac2.begin(), fac2.end(), b[i] - a[i] + 1) - fac2.begin();
		ret += 1ll * (a[i] % mod) * cnt2.query(0, k2-1) % mod + sum4.query(0, k2-1);
		ret %= mod;
		ret += 1ll * b[i] * cnt2.query(k2, n-1) % mod + sum3.query(k2, n-1);
		ret %= mod;
		/*
		for(int j=i+1; j<e; j++){
			if(b[i] + a[i] < a[j] - b[j]){
				ret += b[i] + b[j];
			}
			else{
				ret += a[j] - a[i];
			}
			ret %= mod;
		}
		for(int j=e; j<=n; j++){
			if(b[i] - a[i] < l - a[j] - b[j]){
				ret += b[i] + b[j];
			}
			else{
				ret += l - a[j] + a[i];
			}
			ret %= mod;
		}*/
	}
	printf("%lld\n", ret);
}

lint dis[1000005];

void dijkstra(){
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push(pi(0, n+1));
	memset(dis, 0x3f, sizeof(dis));
	dis[n+1] = 0;
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
		if(dis[x.second] != x.first) continue;
		if(x.second == n+1){
			for(int i=1; i<=n; i++){
				if(dis[i] > dis[x.second] + b[i]){
					dis[i] = dis[x.second] + b[i];
					pq.push(pi(dis[i], i));
				}
			}
		}
		else{
			int i = x.second;
			if(i == 1){
				if(dis[n] > dis[1] + a[n]){
					dis[n] = dis[1] + a[n];
					pq.push(pi(dis[n], n));
				}
			}
			else{
				if(dis[i-1] > dis[i] + a[i-1]){
					dis[i-1] = dis[i] + a[i-1];
					pq.push(pi(dis[i-1], i-1));
				}
			}
			if(i == n){
				if(dis[1] > dis[n] + a[n]){
					dis[1] = dis[n] + a[n];
					pq.push(pi(dis[1], 1));
				}
			}
			else{
				if(dis[i+1] > dis[i] + a[i]){
					dis[i+1] = dis[i] + a[i];
					pq.push(pi(dis[i+1], i+1));
				}
			}
		}
	}
	for(int i=1; i<=n; i++) b[i] = dis[i];
}

void input(){
	int p, q, r, s;
	cin >> n;
	l = 0;
	cin >> a[1] >> p >> q >> r >> s;
	for(int i=2; i<=n; i++){
		a[i] = (1ll * p * a[i-1] + q) % r + s;
	}
	cin >> b[1] >> p >> q >> r >> s;
	for(int i=2; i<=n; i++){
		b[i] = (1ll * p * b[i-1] + q) % r + s;
	}
}

int main(){
	int t;
	scanf("%d",&t);
	for(int i=1; i<=t; i++){
		printf("Case #%d: ", i);
		input();
		solve();
	}
}