結果

問題 No.5021 Addition Pyramid
ユーザー てんぷら
提出日時 2025-02-25 21:07:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 4,002 bytes
コンパイル時間 6,887 ms
コンパイル使用メモリ 334,176 KB
実行使用メモリ 6,824 KB
スコア 168,905,637
最終ジャッジ日時 2025-02-25 21:07:36
合計ジャッジ時間 8,826 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
using namespace std;
using namespace atcoder;
using mint = modint998244353;
const int inf = 1000000007;
const ll longinf = 1ll << 60;

const int N = 50;
const int mod = 100000000;
int a[N][N];

inline int calc_diff(int x, int y) {
    int diff = abs(x - y);
    return min(diff, mod - diff);
}

vector<int> create_next_row(vector<int> &prv, int diff) {
    int m = prv.size();
    int s = 0;
    vector<pair<int, int>> segs;
    rep(i, m + 1) {
        if(i % 2 == 0) {
            // a-diff <=  x + s <= a + diff
            // a - s - diff <= x <= a - s + diff
            int l = a[m][i] - s - diff;
            int r = a[m][i] - s + diff;
            while(l < 0) {
                l += mod;
                r += mod;
            }
            if(r < mod) {
                segs.push_back({l, 1});
                segs.push_back({r, -1});
            } else {
                segs.push_back({l, 1});
                segs.push_back({mod, -1});
                segs.push_back({0, 1});
                segs.push_back({r - mod, -1});
            }
        } else {
            // a-diff <=  -x + s <= a + diff
            // a - s - diff <= -x <= a - s + diff
            // s - a - diff <= x <= a - s - diff;
            int l = s - a[m][i] - diff;
            int r = s - a[m][i] + diff;
            while(l < 0) {
                l += mod;
                r += mod;
            }
            assert(r - l <= mod);
            if(r < mod) {
                segs.push_back({l, 1});
                segs.push_back({r, -1});
            } else {
                segs.push_back({l, 1});
                segs.push_back({mod, -1});
                segs.push_back({0, 1});
                segs.push_back({r - mod, -1});
            }
        }
        if(i != m) {
            s = (mod + prv[i] - s) % mod;
        }
    }
    sort(segs.begin(), segs.end());
    int c = 0;
    int target = -1;
    for(auto [v, sgn] : segs) {
        c += sgn;
        if(c == m + 1) {
            target = v;
            break;
        }
    }
    if(target == -1) {
        return vector<int>();
    } else {
        vector<int> ret(m + 1);
        int s = 0;
        rep(i, m + 1) {
            if(i % 2 == 0) {
                ret[i] = (target + s) % mod;
            } else {
                ret[i] = (mod - target + s) % mod;
            }
            s = (mod + prv[i] - s) % mod;
        }
        return ret;
    }
}

void input() {
    int _;
    cin >> _;
    rep(i, N) {
        rep(j, i + 1) cin >> a[i][j];
    }
}

int evaluate(vector<int> &c) {
    vector<vector<int>> ans(N, vector(N, 0));
    rep(i, N) ans[N - 1][i] = c[i];
    int max_diff = 0;
    for(int i = N - 2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            ans[i][j] = (ans[i + 1][j] + ans[i + 1][j + 1]) % mod;
            int diff = abs(ans[i][j] - a[i][j]);
            max_diff = max(max_diff, min(diff, mod - diff));
        }
    }
    return max_diff;
}

void output(vector<int> &c) {
    rep(i, N) cout << c[i] << " \n"[i + 1 == N];
    cerr << evaluate(c) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    vector<int> ans = {a[0][0]};
    rep(turn, N - 1) {
        int ok = mod, ng = 0;
        while(ok - ng > 1) {
            int mid = (ok + ng) / 2;
            auto ret = create_next_row(ans, mid);
            if(ret.size() > 0) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        // cerr << ok << endl;
        ans = create_next_row(ans, ok);
        // for(auto e : ans)
        //     cout << e << " ";
        // cout << endl;
        // rep(j, turn + 2) {
        //     cout << a[turn + 1][j] << " ";
        // }
        // cout << endl;
    }
    output(ans);
    return 0;
}
0