結果

問題 No.8105 Міжнародний підрядок саміт
コンテスト
ユーザー wasd314
提出日時 2026-08-20 14:33:18
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 2,870 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,287 ms
コンパイル使用メモリ 215,316 KB
実行使用メモリ 731,008 KB
最終ジャッジ日時 2026-08-20 14:33:53
合計ジャッジ時間 16,637 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1
other MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <bit>
#include <bitset>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
int main() {
    using namespace std;
    using lint = long long;
    constexpr lint oo = 1e18;

    auto build = [&](int n) {
        const int n2 = 1 << n;
        const int nn = n + 1;
        const int mid = n * (n + 1) / 2;
        const int mid2 = mid * 2 + 1;
        vector available(nn, vector<bitset<200>>(n2));
        available[0][0].set(mid);
        for (int i = 0; i < n; ++i) {
            for (int sub = 0; sub < (1 << i); ++sub) {
                int bit = 1 << i | sub;
                for (int p = 0; p < popcount((unsigned)bit); ++p) {
                    available[p + 1][bit] |= available[p][sub] << i;
                    available[p][bit] |= available[p][sub] >> i;
                }
            }
        }
        vector le(nn, vector(n2, vector(mid2, oo)));
        vector ge{le};
        for (int bit = 1; bit < n2; ++bit) {
            for (int p = 0; p <= popcount((unsigned)bit); ++p) {
                auto &av = available[p][bit];
                auto le_ = le[p][bit].begin() + mid;
                auto ge_ = ge[p][bit].begin() + mid;
                if (av.test(mid - mid)) le_[-mid] = -mid;
                for (int i = -mid + 1; i <= mid; ++i)
                    le_[i] = av.test(mid + i) ? i : le_[i - 1];
                if (av.test(mid + mid)) ge_[mid] = mid;
                for (int i = mid; i-- > -mid;)
                    ge_[i] = av.test(mid + i) ? i : ge_[i + 1];
            }
        }
        return pair{le, ge};
    };
    map<int, decltype(build(13))> cache;
    for (int n : {2, 3, 5, 7, 11, 13}) cache[n] = build(n);

    auto solve = [&] {
        int n;
        lint mod;
        cin >> n >> mod;
        vector<lint> a(n);
        for (auto &e : a) cin >> e;
        if (n <= 1) return 0ll;
        if (a[1] < a[0]) ranges::reverse(a);
        lint a0 = a[0], d = a[1] - a[0];
        if (d == 0) return (a0 << n - 1) % mod;

        const auto &[le, ge] = cache[n];
        lint ans = 0;
        const int n2 = 1 << n;
        const int mid = n * (n + 1) / 2;
        for (int bit = 1; bit < n2; ++bit) {
            lint ansi = oo;
            int bc = popcount((unsigned)bit);
            for (int p = 0; p <= bc; ++p) {
                lint ca = 2 * p - bc;
                int x0 = -ca * a0 / d;
                if (x0 < 0 && -ca * a0 % d) x0--;
                lint xl = le[p][bit][mid + max(x0, -mid)];
                lint xr = ge[p][bit][mid + min(x0 + 1, mid)];
                lint sl = abs(ca * a0 + xl * d);
                lint sr = abs(ca * a0 + xr * d);
                ansi = min({ansi, sl, sr});
            }
            ans += ansi;
        }
        return ans % mod;
    };
    int t;
    cin >> t;
    for (int ti = 0; ti < t; ++ti) cout << solve() << "\n";
}
0