結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー hirayuu_yc
提出日時 2025-02-24 09:42:07
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 821 ms / 2,000 ms
コード長 1,962 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,392 ms
コンパイル使用メモリ 119,552 KB
実行使用メモリ 6,820 KB
スコア 41,428,954
最終ジャッジ日時 2025-02-25 19:32:33
合計ジャッジ時間 51,381 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

const int MODULO = 100000000;
const int MOD_STEP = 50000000;

// 誤差を求める関数
int gosa(int x, int y) {
    return min(abs(x - y), MODULO - abs(x - y));
}

int main() {
    srand(time(0)); // 乱数のシード設定
    int N;
    cin >> N;
    vector<vector<int>> c(N, vector<int>(N));
    
    // 入力の読み取り
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> c[i][j];
        }
    }
    
    vector<int> ans(N, 0);
    int nsc = 0;
    
    // 初期の最大誤差を求める
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            nsc = max(nsc, gosa(c[i][j], 0));
        }
    }
    
    int mod = MOD_STEP;
    
    while (mod >= 1) {
        for (int j = 0; j < 12000; ++j) {
            int pos = rand() % N; // ランダムな位置を選択
            int add = (rand() % 2) * 2 - 1; // -1または1を選択
            
            vector<int> nt = ans;
            nt[pos] = (nt[pos] + add * mod + MODULO) % MODULO;
            
            int mx = 0;
            
            for (int k = N - 1; k >= 0; --k) {
                for (int l = 0; l <= k; ++l) {
                    mx = max(mx, gosa(nt[l], c[k][l]));
                }
                vector<int> new_nt(k);
                for (int l = 0; l < k; ++l) {
                    new_nt[l] = (nt[l] + nt[l + 1]) % MODULO;
                }
                nt = new_nt;
            }
            
            if (nsc >= mx) {
                nsc = mx;
                ans[pos] = (ans[pos] + add * mod + MODULO) % MODULO;
            }
        }
        mod >>= 1;
    }
    
    for (int i = 0; i < N; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;
    
    return 0;
}
0