結果
問題 | No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ |
ユーザー | tnakao0123 |
提出日時 | 2023-12-11 19:01:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 212 ms / 3,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 667 ms |
コンパイル使用メモリ | 56,780 KB |
実行使用メモリ | 6,676 KB |
最終ジャッジ日時 | 2023-12-11 19:01:32 |
合計ジャッジ時間 | 3,997 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
6,676 KB |
testcase_01 | AC | 7 ms
6,676 KB |
testcase_02 | AC | 13 ms
6,676 KB |
testcase_03 | AC | 60 ms
6,676 KB |
testcase_04 | AC | 41 ms
6,676 KB |
testcase_05 | AC | 9 ms
6,676 KB |
testcase_06 | AC | 50 ms
6,676 KB |
testcase_07 | AC | 48 ms
6,676 KB |
testcase_08 | AC | 14 ms
6,676 KB |
testcase_09 | AC | 34 ms
6,676 KB |
testcase_10 | AC | 47 ms
6,676 KB |
testcase_11 | AC | 13 ms
6,676 KB |
testcase_12 | AC | 61 ms
6,676 KB |
testcase_13 | AC | 71 ms
6,676 KB |
testcase_14 | AC | 61 ms
6,676 KB |
testcase_15 | AC | 55 ms
6,676 KB |
testcase_16 | AC | 58 ms
6,676 KB |
testcase_17 | AC | 58 ms
6,676 KB |
testcase_18 | AC | 68 ms
6,676 KB |
testcase_19 | AC | 74 ms
6,676 KB |
testcase_20 | AC | 72 ms
6,676 KB |
testcase_21 | AC | 72 ms
6,676 KB |
testcase_22 | AC | 212 ms
6,676 KB |
testcase_23 | AC | 195 ms
6,676 KB |
testcase_24 | AC | 186 ms
6,676 KB |
testcase_25 | AC | 179 ms
6,676 KB |
testcase_26 | AC | 187 ms
6,676 KB |
testcase_27 | AC | 7 ms
6,676 KB |
testcase_28 | AC | 7 ms
6,676 KB |
testcase_29 | AC | 147 ms
6,676 KB |
testcase_30 | AC | 31 ms
6,676 KB |
testcase_31 | AC | 62 ms
6,676 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 2581.cc: No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ const int N = 28; const int K = N / 2; const int KBITS = 1 << K; /* typedef */ typedef vector<int> vi; /* global variables */ int gs[N], hs[N]; vi bv0[K + 1], bv1[K + 1]; /* subroutines */ void addmod(int &a, int b, int m) { a = (a + b) % m; } /* main */ int main() { int m; scanf("%d", &m); for (int i = 0; i < N; i++) scanf("%d", gs + i); for (int i = 0; i < N; i++) scanf("%d", hs + i); for (int bits = 0; bits < KBITS; bits++) { int bn = 0, s0 = 0, s1 = 0; for (int i = 0, bi = 1; i < K; i++, bi <<= 1) { bn += ((bits >> i) & 1); addmod(s0, (bits & bi) ? gs[i] : hs[i], m); addmod(s1, (bits & bi) ? gs[K + i] : hs[K + i], m); } bv0[bn].push_back(s0); bv1[bn].push_back(s1); } for (int i = 0; i <= K; i++) { sort(bv0[i].begin(), bv0[i].end()); sort(bv1[i].begin(), bv1[i].end()); } int qn; scanf("%d", &qn); while (qn--) { int ki, xi; scanf("%d%d", &ki, &xi); int cnt = 0; for (int i = 0, j = ki; j >= 0; i++, j--) if (i <= K && j <= K && ! bv0[i].empty() && ! bv1[j].empty()) for (auto u: bv0[i]) { auto vit0 = bv1[j].begin(), vit1 = bv1[j].end(); auto l0 = lower_bound(vit0, vit1, xi - u); auto l1 = lower_bound(vit0, vit1, m - u); auto l2 = lower_bound(vit0, vit1, m + xi - u); cnt += (l1 - l0) + (vit1 - l2); } printf("%d\n", cnt); } return 0; }