fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair < int, int > ii;
  7.  
  8. const int N = 55;
  9. const int mod = 1e9 + 7;
  10.  
  11. inline int add(int x, int y) {
  12.   return x + y >= mod ? x + y - mod : x + y;
  13. }
  14.  
  15. inline int mul(int x, int y) {
  16.   return (ll) x * y % mod;
  17. }
  18.  
  19. inline int fe(int x, int k) {
  20.   int res = 1;
  21.   while(k) {
  22.     if(k & 1)
  23.       res = mul(res, x);
  24.     x = mul(x, x);
  25.     k >>= 1;
  26.   }
  27.   return res;
  28. }
  29.  
  30. inline int dv(int x, int k) {
  31.   return mul(x, fe(k, mod - 2));
  32. }
  33.  
  34. int n, s, e;
  35. ii a[N];
  36. int pw[N];
  37. int dp[N][N][N][2];
  38.  
  39. #define UP 1
  40. #define DOWN 2
  41. #define LEFT 4
  42. #define RIGHT 8
  43. #define c(x, y) (!!(x&y))
  44.  
  45. int f(int x, int ms, int me, bool done) {
  46.   if(x > n)
  47.     return done;
  48.   int &r = dp[x][ms][me][done];
  49.   if(r != -1) return r;
  50.   if(x == s)
  51.     return r = f(x + 1, 0, me, done);
  52.   if(x == e)
  53.     return r = f(x + 1, ms, N - 1, done);
  54.   r = 0;
  55.   for(int i = 1; i < 16; i += i) {
  56.     bool d = done;
  57.     d |= x < s and c(i, UP) and ms <= a[x].second;
  58.     d |= x > s and c(i, LEFT) and ms >= a[x].second;
  59.     d |= x < e and c(i, DOWN) and me >= a[x].second;
  60.     d |= x > e and c(i, LEFT) and me <= a[x].second;
  61.     int nms = ms, nme = me;
  62.     if(x < s and c(i, RIGHT))
  63.       nms = min(nms, a[x].second);
  64.     if(x > s and c(i, UP))
  65.       nms = max(nms, a[x].second);
  66.  
  67.     if(x < e and c(i, RIGHT))
  68.       nme = max(nme, a[x].second);
  69.     if(x > e and c(i, DOWN))
  70.       nme = min(nme, a[x].second);
  71.     r = add(r, f(x + 1, nms, nme, d));
  72.   }
  73.   return r;
  74. }
  75.  
  76. void solve() {
  77.   scanf("%d %d %d", &n, &s, &e);
  78.   for(int i = 1; i <= n; i++) {
  79.     scanf("%d %d", &a[i].first, &a[i].second);
  80.     swap(a[i].first, a[i].second);
  81.   }
  82.   a[++n] = {s, 0};
  83.   a[++n] = {e, 1e9};
  84.   sort(a + 1, a + n + 1);
  85.   for(int i = 1; i <= n; i++) {
  86.     if(a[i].second == 0)
  87.       s = i;
  88.     if(a[i].second == 1e9)
  89.       e = i;
  90.   }
  91.   vector < int > vx, vy;
  92.   for(int i = 1; i <= n; i++)
  93.     vx.push_back(a[i].first), vy.push_back(a[i].second);
  94.   sort(vx.begin(), vx.end());
  95.   vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
  96.   sort(vy.begin(), vy.end());
  97.   vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
  98.   for(int i = 1; i <= n; i++) {
  99.     a[i].first = lower_bound(vx.begin(), vx.end(), a[i].first) - vx.begin() + 1;
  100.     a[i].second = lower_bound(vy.begin(), vy.end(), a[i].second) - vy.begin() + 1;
  101.   }
  102.   memset(dp, -1, sizeof(dp));
  103.   printf("%d\n", f(1, N - 1, 0, 0));
  104. }
  105.  
  106. int main() {
  107.   freopen("in2.txt", "r", stdin);
  108.   freopen("out.txt", "w", stdout);
  109.   int tt;
  110.   scanf("%d", &tt);
  111.   for(int t = 1; t <= tt; t++) {
  112.     printf("Case #%d: ", t);
  113.     solve();
  114.   }
  115.   return 0;
  116. }
  117.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D1DMBH
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!