Submission #217598

#TimeUsernameProblemLanguageResultExecution timeMemory
217598BTheroRuins 3 (JOI20_ruins3)C++17
0 / 100
6092 ms12836 KiB
// chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> //#include<ext/pb_ds/tree_policy.hpp> //#include<ext/pb_ds/assoc_container.hpp> #define __DBG 1 #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) if (__DBG) cerr << #x << " = " << x << endl; using namespace std; //using namespace __gnu_pbds; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; const int MOD = (int)1e9 + 7; int cnt[15]; int pw[15]; bool my[26]; int n; int addMod(int a, int b, int m = MOD) { a += b; if (m <= a) { a -= m; } return a; } int bit(int x, int p) { return (x / pw[p]) % 3; } void solve() { scanf("%d", &n); for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); my[x - 1] = 1; } pw[0] = 1; for (int i = 1; i < 15; ++i) { pw[i] = pw[i - 1] * 3; } vector<int> dp(pw[n], 0); dp[0] = 1; // 2 3 3 1 for (int i = 2 * n - 1; i >= 0; --i) { vector<int> ndp(pw[n], 0); for (int mask = 0; mask < pw[n]; ++mask) { fill(cnt, cnt + n, 0); for (int j = n - 1; j >= 0; --j) { int c = bit(mask, j); cnt[j] += c; if (cnt[j] > 1) { if (j > 0) { cnt[j - 1] += cnt[j] - 1; } cnt[j] = 1; } } int p = 0; while (cnt[p]) { ++p; } if (my[i]) { for (int j = p; j < n; ++j) { int c = bit(mask, j); if (c != 2) { int nmask = mask + pw[j]; ndp[nmask] = addMod(ndp[nmask], dp[mask]); } } } else { for (int j = 0; j < p; ++j) { int c = bit(mask, j); if (c != 2) { int nmask = mask + pw[j]; ndp[nmask] = addMod(ndp[nmask], dp[mask]); } } } } dp = ndp; } printf("%d\n", dp[pw[n] - 1]); } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

ruins3.cpp: In function 'void solve()':
ruins3.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
ruins3.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...