Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
FBHC17 R3 Solution
#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();
}
}
#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();
}
}
#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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment