Instantly share code, notes, and snippets.

koosaga/fb17r3a.cpp Created Jan 29, 2017

FBHC17 R3 Solution
 #include using namespace std; typedef long long lint; typedef pair 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 'Z'){ puts("-1"); return; } } } cout << str << endl; int arr[1005]; for(int i=0; i
 #include using namespace std; typedef long long lint; typedef pair 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 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[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 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>= 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> b[1] >> ka; p = 2; for(int i=0; i