結果
問題 |
No.5021 Addition Pyramid
|
ユーザー |
![]() |
提出日時 | 2025-02-28 12:10:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,953 ms / 2,000 ms |
コード長 | 5,882 bytes |
コンパイル時間 | 7,672 ms |
コンパイル使用メモリ | 351,248 KB |
実行使用メモリ | 6,820 KB |
スコア | 235,384,520 |
最終ジャッジ日時 | 2025-02-28 12:12:07 |
合計ジャッジ時間 | 109,301 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace atcoder; using namespace __gnu_pbds; using mint = modint998244353; #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define print(var) std::cout<<#var<<"="<<(var)<<std::endl #define all(a) (a).begin(), (a).end() #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define ll long long #define vll vector<ll> #define vvll vector<vll> #define vvvll vector<vvll> #define vvvvll vector<vvvll> #define vmi vector<mint> #define vvmi vector<vmi> #define vvvmi vector<vvmi> #define vvvvmi vector<vvvmi> #define vvvvvmi vector<vvvvmi> #define vs vector<string> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define bit(x,i)(((x)>>(i))&1) #define inf (1<<30) #define INF (1ll<<60) #define X first #define Y second template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } template<class T, class F> T nibutan(T ok, T ng, const F &f){while(abs(ok-ng)>1){T mid = (ok+ng)/2;(f(mid)?ok:ng) = mid;}return ok;} template<class T> vector<T> digit(T x){vector<T> res; while(x>0){res.push_back(x%10); x/=10;} return res;} ostream& operator<<(ostream& os, const mint& x){ os << x.val(); return os; } template<class T> istream &operator>>(istream &is, vector<T> &vec){ for(auto &v:vec) is >> v; return is; } template<class T> void coutvector(vector<T> x){ for(int i=0;i<(int)x.size();i++){if(i>0) cout<<" ";cout<<x[i];}cout<<endl;} using Set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; template<class S, class T> using Unordered_Map = gp_hash_table<S,T>; #ifdef LOCAL #include<dump.hpp> CPP_DUMP_DEFINE_EXPORT_OBJECT(mint,val()); #else #define cpp_dump #endif static uint32_t xor128(void){ static uint32_t x=123456789,y=362436069,z=521288629,w=88675123; uint32_t t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } inline int randrange(int a){return (uint64_t(xor128()) * a >> 32); } inline int randrange(int a, int b){ return randrange(b-a)+a; } inline double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;} inline double get_time() { #ifdef ONLINE_JUDGE timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec * 1e3 + tv.tv_usec * 1e-3; #else using namespace std::chrono; return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count(); #endif } double start_time = get_time(); inline double elapsed(){ return get_time() - start_time; } constexpr int N = 50; constexpr int MOD = 100000000; int a[N][N]; inline int diff(int x,int y){ return min(abs(x-y),MOD-abs(x-y)); } struct State{ int c[N]; State(){ init(); } int get_score(){ int score = 0; int b[N],nb[N]; for(int i=0;i<N;i++) b[i] = c[i]; for(int i=N-1;i>=0;i--){ for(int j=0;j<=i;j++){ int diff = min(abs(a[i][j]-b[j]),MOD-abs(a[i][j]-b[j])); chmax(score,diff); } if(i>0){ for(int j=0;j<i;j++){ nb[j] = (b[j]+b[j+1]); if(nb[j]>=MOD) nb[j]-=MOD; } swap(b,nb); } } return score; } int move_sim(vi idx, vi x){ vi old(idx.size()); for(int i=0;i<idx.size();i++){ old[i] = c[idx[i]]; c[idx[i]] = x[i]; } int score = get_score(); for(int i=0;i<idx.size();i++){ c[idx[i]] = old[i]; } return score; } int move_sim(int i,int x){ int old = c[i]; c[i] = x; int score = get_score(); c[i] = old; return score; } void move(int i, int x){ c[i] = x; return; } void move(vi idx, vi x){ for(int i=0;i<idx.size();i++){ c[idx[i]] = x[i]; } return; } void init(int top=-1){ vvi b(N,vi(N)); if(top==-1) b[0][0] = a[0][0]; else b[0][0] = top; for(int i=1;i<N;i++){ b[i][0] = 0; for(int j=1;j<=i;j++) b[i][j] = (b[i-1][j-1]-b[i][j-1]+MOD)%MOD; vi tmp; for(int j=0;j<=i;j++){ if(j&1) tmp.push_back((b[i][j]-a[i][j]+MOD)%MOD); else tmp.push_back((a[i][j]-b[i][j]+MOD)%MOD); } sort(all(tmp)); tmp.push_back(tmp.front()+MOD); int mx=-1,mid=0; for(int j=0;j<=i;j++){ if(chmax(mx,tmp[j+1]-tmp[j])) mid = ((tmp[j+1]+tmp[j])/2 + MOD/2)%MOD; } b[i][0] = mid; for(int j=1;j<=i;j++) b[i][j] = (b[i-1][j-1]-b[i][j-1]+MOD)%MOD; } for(int i=0;i<N;i++) c[i] = b[N-1][i]; } void out(){ for(int i=0;i<N;i++){ if(i>0) cout << " "; cout << c[i]; } cout << endl; } }; void in(){ int tmp; cin>>tmp; for(int i=0;i<N;i++)for(int j=0;j<=i;j++){ cin>>a[i][j]; } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); in(); State state; int best_score = state.get_score(); State best_state = state; int iter = 0; while(elapsed()<1950){ int top = randrange(MOD); state.init(top); int next_score = state.get_score(); if(chmin(best_score,next_score)){ cerr << "score : " << best_score << endl; best_state = state; } iter++; } cerr << "score : " << best_score << endl; cerr << "true score : " << MOD/2 - best_score << endl; cerr << "total_iter : " << iter << endl; best_state.out(); }