Submission #44035

#	Time	Username	Problem	Language	Result	Execution time	Memory
44035		wxh010910	Security Gate (JOI18_security_gate)	C++17	100 / 100	2065 ms	888392 KiB

securitygate

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 305;
const int mod = 1e9 + 7;

int n, ans, a[N];
char s[N];

namespace CaseA {
  int f[N][N];

  int Main() {
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      if (a[i] >= 0) {
        for (int j = 0; j <= i; ++j) {
          f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
        }
      }
      if (a[i] <= 0) {
        for (int j = 1; j <= i; ++j) {
          f[i + 1][j - 1] = (f[i + 1][j - 1] + f[i][j]) % mod;
        }
      }
    }
    ans = (ans + f[n][0]) % mod;
    return 0;
  }
}

namespace CaseB {
  int h[N][N], f[N][N][N][2], g[N][N][N][2];

  inline void Init() {
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    memset(h, 0, sizeof h);
    for (int x = 0; x < n >> 1; ++x) {
      f[x][0][0][!x] = 1;
      for (int i = 0; i < n; ++i) {
        if (a[i] >= 0) {
          for (int j = 0; j < x; ++j) {
            f[x][i + 1][j + 1][j + 1 == x] = (f[x][i + 1][j + 1][j + 1 == x] + f[x][i][j][0]) % mod;
            f[x][i + 1][j + 1][1] = (f[x][i + 1][j + 1][1] + f[x][i][j][1]) % mod;
          }
        }
        if (a[i] <= 0) {
          for (int j = 0; j < x; ++j) {
            f[x][i + 1][j][0] = (f[x][i + 1][j][0] + f[x][i][j + 1][0]) % mod;
            f[x][i + 1][j][1] = (f[x][i + 1][j][1] + f[x][i][j + 1][1]) % mod;
          }
        }
      }
    }
    for (int x = 0; x < n; ++x) {
      g[x][n][0][!x] = 1;
      for (int i = n - 1; ~i; --i) {
        if (a[i] >= 0) {
          for (int j = 0; j < n; ++j) {
            g[x][i][j][0] = (g[x][i][j][0] + g[x][i + 1][j + 1][0]) % mod;
          }
          g[x][i][x][1] = (g[x][i][x][1] + g[x][i + 1][x + 1][0]) % mod;
          for (int j = x + 1; j < min(n, x << 1); ++j) {
            g[x][i][j][1] = (g[x][i][j][1] + g[x][i + 1][j + 1][1]) % mod;
          }
        }
        if (a[i] <= 0) {
          for (int j = 0; j < n; ++j) {
            g[x][i][j + 1][0] = (g[x][i][j + 1][0] + g[x][i + 1][j][0]) % mod;
          }
          if (x) {
            g[x][i][x][1] = (g[x][i][x][1] + g[x][i + 1][x - 1][0]) % mod;
          }
          for (int j = x; j <= min(n, x << 1); ++j) {
            g[x][i][j + 1][1] = (g[x][i][j + 1][1] + g[x][i + 1][j][1]) % mod;
          }
        }
      }
    }
    h[n][0] = 1;
    for (int i = n - 1; ~i; --i) {
      if (a[i] >= 0) {
        for (int j = 0; j < n; ++j) {
          h[i][j] = (h[i][j] + h[i + 1][j + 1]) % mod;
        }
      }
      if (a[i] <= 0) {
        for (int j = 0; j < n; ++j) {
          h[i][j + 1] = (h[i][j + 1] + h[i + 1][j]) % mod;
        }
      }
    }
  }

  inline void Solve(int x, int y) {
    for (int i = 0; i < n; i += 2) {
      if (a[i] <= 0) {
        if (x >= y) {
          ans = (1LL * f[x][i][0][1] * h[i + 1][(y << 1) - 1] + ans) % mod;
        } else {
          ans = (1LL * f[x][i][0][1] * g[x + y][i + 1][(y << 1) - 1][1] + ans) % mod;
        }
      }
    }
  }

  inline void Solve() {
    for (int i = 0; i <= n >> 1; ++i) {
      for (int j = 1; i + j <= n >> 1; ++j) {
        Solve(i, j);
      }
    }
  }

  int Main() {
    for (int t = 0; t < 2; ++t) {
      Init(), Solve();
      reverse(a, a + n);
      for (int i = 0; i < n; ++i) {
        a[i] = -a[i];
      }
    }
    return 0;
  }
}

namespace CaseC {
  int f[N >> 1][N][N][2], g[N >> 1][N][N << 1][3];

  inline void Init(int t) {
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    for (int x = 0; x < n >> 1; ++x) {
      f[x][0][0][!x] = 1;
      for (int i = 0; i < n; ++i) {
        if (a[i] >= 0) {
          for (int j = 0; j < x; ++j) {
            f[x][i + 1][j + 1][j + 1 == x] = (f[x][i + 1][j + 1][j + 1 == x] + f[x][i][j][0]) % mod;
            f[x][i + 1][j + 1][1] = (f[x][i + 1][j + 1][1] + f[x][i][j][1]) % mod;
          }
        }
        if (a[i] <= 0) {
          for (int j = 0; j < x; ++j) {
            f[x][i + 1][j][0] = (f[x][i + 1][j][0] + f[x][i][j + 1][0]) % mod;
            f[x][i + 1][j][1] = (f[x][i + 1][j][1] + f[x][i][j + 1][1]) % mod;
          }
        }
      }
    }
    for (int x = 0; x < n >> 1; ++x) {
      g[x][n][n][!x && !t] = 1;
      for (int i = n - 1; ~i; --i) {
        if (a[i] >= 0) {
          for (int j = 1; j < n; ++j) {
            g[x][i][j - 1 + n][0] = (g[x][i][j - 1 + n][0] + g[x][i + 1][j + n][0]) % mod;
          }
          for (int j = 0; j < n; ++j) {
            g[x][i][j - 1 + n][1 + (!j)] = (g[x][i][j - 1 + n][1 + (!j)] + g[x][i + 1][j + n][1]) % mod;
          }
          for (int j = -n + 1; j <= x << 1; ++j) {
            g[x][i][j - 1 + n][2] = (g[x][i][j - 1 + n][2] + g[x][i + 1][j + n][2]) % mod;
          }
        }
        if (a[i] <= 0) {
          for (int j = 0; j < n; ++j) {
            g[x][i][j + 1 + n][j + 1 == x + t] = (g[x][i][j + 1 + n][j + 1 == x + t] + g[x][i + 1][j + n][0]) % mod;
          }
          for (int j = 0; j < n; ++j) {
            g[x][i][j + 1 + n][1] = (g[x][i][j + 1 + n][1] + g[x][i + 1][j + n][1]) % mod;
          }
          for (int j = -n; j < x << 1; ++j) {
            g[x][i][j + 1 + n][2] = (g[x][i][j + 1 + n][2] + g[x][i + 1][j + n][2]) % mod;
          }
        }
      }
    }
  }

  inline void Solve(int x, int y) {
    for (int i = 0; i < n; i += 2) {
      if (a[i] <= 0) {
        ans = (1LL * f[x][i][0][1] * g[x + y][i + 1][(y << 1) - 1 + n][2] + ans) % mod;
      }
    }
  }

  inline void Solve() {
    for (int i = -(n >> 1) + 1; i < (n >> 1); ++i) {
      for (int j = max(0, -i); j + abs(i) <= n >> 1; ++j) {
        Solve(j, i);
      }
    }
  }

  int Main() {
    for (int t = 0; t < 2; ++t) {
      Init(t), Solve();
      reverse(a, a + n);
      for (int i = 0; i < n; ++i) {
        a[i] = -a[i];
      }
    }
    return 0;
  }
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), scanf("%s", s);
  if (n & 1) {
    puts("0");
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    if (s[i] == '(') {
      a[i] = 1;
    } else if (s[i] == ')') {
      a[i] = -1;
    } else {
      a[i] = 0;
    }
  }
  CaseA::Main();
  CaseB::Main();
  CaseC::Main();
  printf("%d\n", ans);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}

Compilation message (stderr)

securitygate.cpp: In function 'int main()':
securitygate.cpp:249:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   Read(n), scanf("%s", s);
   ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 43 / 43
• Subtask 5: 27 / 27