Submission #781203

#TimeUsernameProblemLanguageResultExecution timeMemory
781203skittles1412Linear Garden (IOI08_linear_garden)C++17
100 / 100
386 ms25900 KiB
#include "bits/extc++.h" using namespace std; template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \ << ": "; \ dbgh(__VA_ARGS__) #else #define cerr \ if (false) \ cerr #define dbg(...) #endif using i8 = int8_t; #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) int MOD; struct mint { static int norm(long x) { x %= MOD; if (x < 0) { x += MOD; } return int(x); } int x; mint() : x(0) {} mint(long x) : x(norm(x)) {} static mint from_unchecked(int x) { mint m; m.x = x; return m; } friend ostream& operator<<(ostream& out, const mint& m) { return out << m.x; } mint operator-() const { if (!x) { return {}; } else { return mint::from_unchecked(MOD - x); } } mint& operator+=(const mint& m) { x += m.x; if (x >= MOD) { x -= MOD; } return *this; } mint& operator-=(const mint& m) { return *this += -m; } mint& operator*=(const mint& m) { x = int(long(x) * m.x % MOD); return *this; } friend mint operator+(mint a, const mint& b) { return a += b; } friend mint operator-(mint a, const mint& b) { return a -= b; } friend mint operator*(mint a, const mint& b) { return a *= b; } }; struct Solver { int n, ql, qr; const vector<i8>& arr; vector<array<mint, 6>> memo; Solver(const vector<i8>& arr, int ql, int qr) : n(sz(arr)), arr(arr), ql(ql), qr(qr), memo(n) { for (auto& a : memo) { a.fill(mint::from_unchecked(-1)); } } mint dp(int ind, int psum, bool lt) { if (!(ql <= psum && psum <= qr)) { return 0; } else if (ind == n) { return lt; } mint& ans = memo[ind][(psum - ql) * 2 + lt]; if (ans.x != -1) { return ans; } ans = 0; for (int x : {-1, +1}) { if (!lt && x > arr[ind]) { continue; } ans += dp(ind + 1, psum + x, lt || (x < arr[ind])); } return ans; } mint solve() { auto id = [&](int psum, bool lt) -> int { return (psum - ql) * 2 + lt; }; array<mint, 6> memo; for (int psum = ql; psum <= qr; psum++) { for (bool lt : {false, true}) { memo[id(psum,lt)] = lt; } } for (int i = n - 1; i >= 0; i--) { array<mint, 6> n_memo; for (int psum = ql; psum <= qr; psum++) { for (bool lt : {false, true}) { mint& ans = n_memo[id(psum, lt)]; ans = 0; for (int x : {-1, +1}) { if (!lt && x > arr[i]) { continue; } ans += dp(i + 1, psum + x, lt || (x < arr[i])); } } } memo = n_memo; } return memo[id(0, false)]; } }; void solve() { int n; cin >> n >> MOD; vector<i8> arr(n); { string s; cin >> s; for (int i = 0; i < n; i++) { if (s[i] == 'L') { arr[i] = -1; } else { assert(s[i] == 'P'); arr[i] = +1; } } } auto solve = [&](int ql, int qr) -> mint { return Solver(arr, ql, qr).solve(); }; cout << solve(-2, 0) + solve(-1, 1) + solve(0, 2) - solve(-1, 0) - solve(0, 1) + 1 << endl; } int main() { cin.tie(nullptr); cin.exceptions(ios::failbit); ios_base::sync_with_stdio(false); solve(); }

Compilation message (stderr)

linear_garden.cpp: In constructor 'Solver::Solver(const std::vector<signed char>&, int, int)':
linear_garden.cpp:93:23: warning: 'Solver::arr' will be initialized after [-Wreorder]
   93 |     const vector<i8>& arr;
      |                       ^~~
linear_garden.cpp:92:12: warning:   'int Solver::ql' [-Wreorder]
   92 |     int n, ql, qr;
      |            ^~
linear_garden.cpp:96:5: warning:   when initialized here [-Wreorder]
   96 |     Solver(const vector<i8>& arr, int ql, int qr)
      |     ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...