結果
問題 |
No.5021 Addition Pyramid
|
ユーザー |
|
提出日時 | 2025-02-25 20:59:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,803 ms / 2,000 ms |
コード長 | 2,878 bytes |
コンパイル時間 | 5,031 ms |
コンパイル使用メモリ | 279,436 KB |
実行使用メモリ | 6,824 KB |
スコア | 1,628,646 |
最終ジャッジ日時 | 2025-02-25 21:01:17 |
合計ジャッジ時間 | 99,397 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
//#pragma GCC optimize("Ofast") //#pragma GCC optimize "O3,omit-frame-pointer,inline" #include <iostream> // cout, endl, cin #include <string> // string, to_string, stoi #include <vector> // vector #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound #include <utility> // pair, make_pair #include <tuple> // tuple, make_tuple #include <cstdint> // int64_t, int*_t #include <cstdio> // printf #include <map> // map #include <queue> // queue, priority_queue #include <set> // set #include <stack> // stack #include <deque> // deque #include <unordered_map> // unordered_map #include <unordered_set> // unordered_set #include <bitset> // bitset #include <cctype> // isupper, islower, isdigit, toupper, tolower #include <iomanip>//fixed,setprecision #include <limits.h>//INT_MAX #include <math.h>//M_PI #include <random> #include <regex> // 正規表現 #include <time.h> #include <fstream> #include <array> #include <bit> #include <chrono> #include <span> #include <cmath> #include <complex>//複素数 //#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; //using mint = modint998244353; using ll = long long; using ull = unsigned long long; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; random_device rnd; mt19937 mt_gen(rnd()); int RandInt(int a, int b) { return a + mt_gen() % (b - a + 1); } const ll MOD=100000000; const int MAX = 100000000; // スコア計算 int score_function(int N, vector<vector<int>> A, vector<int> C) { vector<vector<int>> B(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) B[N - 1][i] = C[i]; for (int i = N - 2; i >= 0; i--) { for (int j = 0; j <= i; j++) B[i][j] = (B[i + 1][j] + B[i + 1][j + 1]) % MAX; } int max_error = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) max_error = max(max_error, min(abs(A[i][j] - B[i][j]), MAX - abs(A[i][j] - B[i][j]))); } return MAX / 2 - max_error; } int main() { // 入力 int N; cin >> N; vector<vector<int>> A(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) cin >> A[i][j]; } double timeLimit = 1.8; // 1.8秒 auto t0 = chrono::steady_clock::now(); vector<int> C(N, 0); ll best_score=0; vector<int> best_C(N,0); while (true) { double elapsed = chrono::duration<double>(chrono::steady_clock::now() - t0).count(); if (elapsed > timeLimit) break; rep(i,N) C[i]=RandInt(0,MAX-1); int score=score_function(N,A,C); if(score>best_score){ best_score=score; best_C=C; } } cerr<<best_score<<endl; // 出力 for (int i = 0; i < N; i++) { if (i >= 1) cout << " "; cout<<C[i]; } cout << endl; return 0; }