結果
問題 | No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ |
ユーザー |
![]() |
提出日時 | 2023-12-09 00:28:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 212 ms / 3,000 ms |
コード長 | 2,129 bytes |
コンパイル時間 | 3,662 ms |
コンパイル使用メモリ | 262,292 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-27 03:20:39 |
合計ジャッジ時間 | 6,603 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; int main() { constexpr int N = 28; int m; cin >> m; array<int, N> g{}, h{}; for (int& g_i : g) cin >> g_i; for (int& h_i : h) cin >> h_i; array<vector<int>, N / 2 + 1> a{}, b{}; REP(bit, 1 << (N / 2)) { int brilliance = 0; REP(i, N / 2) { brilliance += (bit >> i & 1 ? g : h)[i]; brilliance %= m; } a[popcount(static_cast<unsigned>(bit))].emplace_back(brilliance); } REP(i, N / 2 + 1) ranges::sort(a[i]); REP(bit, 1 << (N / 2)) { int brilliance = 0; REP(i, N / 2) { brilliance += (bit >> i & 1 ? g : h)[N / 2 + i]; brilliance %= m; } b[popcount(static_cast<unsigned>(bit))].emplace_back(brilliance); } REP(i, N / 2 + 1) ranges::sort(b[i]); int q; cin >> q; while (q--) { int k, x; cin >> k >> x; int ans = 0; for (int i = max(k - N / 2, 0); i <= k && i <= N / 2; ++i) { const int j = k - i; for (const int a_i : a[i]) { for (const auto [l, r] : array<pair<int, int>, 2>{make_pair(x, m - 1), make_pair(x + m, m * 2 - 1)}) { if (r < a_i) continue; const int ll = max(l - a_i, 0), rr = r - a_i; ans += distance(ranges::lower_bound(b[k - i], ll), ranges::upper_bound(b[k - i], rr)); } } } cout << ans << '\n'; } return 0; }