結果
問題 | No.5021 Addition Pyramid |
ユーザー |
|
提出日時 | 2025-02-25 22:51:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 914 ms / 2,000 ms |
コード長 | 7,405 bytes |
コンパイル時間 | 3,213 ms |
コンパイル使用メモリ | 232,904 KB |
実行使用メモリ | 6,820 KB |
スコア | 264,177,014 |
最終ジャッジ日時 | 2025-02-25 22:52:11 |
合計ジャッジ時間 | 49,865 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
// (◕ᴗ◕✿) // #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define srep(i, s, n) for (ll i = s; i < (n); i++) #define len(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>; using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>; using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>; using uint = unsigned int; using ull = unsigned long long; const int mod = 100000000; const ld pi = 3.141592653589793; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; #define debug(var) do{std::cout << #var << " : \n";view(var);}while(0) template<typename T> void view(T e){cout << e << endl;} template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;} template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } } // #define DEBUG #ifdef DEBUG constexpr bool DEBUGMODE = true; #else constexpr bool DEBUGMODE = false; #endif ofstream wrt; string outputfile = "output.txt", inputfile = "input0.txt"; struct modint { int Mod = mod; int val = 0; using mint = modint; modint() {}; modint(ll v) { if (0 <= v && v < Mod) val = v; else{ v %= Mod; if (v < 0) v += Mod; val = v; } } mint operator++(int){ val++; if (val == Mod) val = 0; return *this; } mint operator--(int){ if (val == 0) val = Mod; val--; return *this; } mint& operator+=(const mint& v){ val += v.val; if (val >= Mod) val -= Mod; return *this; } mint& operator-=(const mint& v){ val -= v.val; if (val < 0) val += Mod; return *this; } mint& operator*=(const mint& v){ val = (int)(1ll * val * v.val % Mod); return *this; } modint inverse() const { int a = val, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b), swap(u -= t * v, v); } return modint(u); } mint pow(ll n) const { mint a = *this, ret = 1; while (n > 0){ if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; } mint& operator>>=(ll k){ *this *= mint(2).pow(k).pow(Mod - 2); return *this; } mint& operator<<=(ll k){ *this *= mint(2).pow(k); return *this; } mint operator/=(const mint& v){ *this *= v.inverse(); return *this; } mint operator-() const { return mint(-val);} friend mint operator+(const mint& u, const mint& v){return mint(u) += v;} friend mint operator-(const mint& u, const mint& v){return mint(u) -= v;} friend mint operator*(const mint& u, const mint& v){return mint(u) *= v;} friend mint operator/(const mint& u, const mint& v){return mint(u) /= v;} friend bool operator==(const mint& u, const mint& v){return u.val == v.val;} friend bool operator!=(const mint& u, const mint& v){return u.val != v.val;} friend bool operator>(const mint& u, const mint& v){return u.val > v.val;} friend bool operator<(const mint& u, const mint& v){return u.val < v.val;} friend mint operator>>(mint& u, const ll k){return u >>= k;} friend mint operator<<(mint& u, const ll k){return u <<= k;} friend ostream& operator<<(ostream& stream, mint& v){ stream << v.val; return stream; } }; using mint = modint; unsigned int randxor(){ static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t; t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int randint(int a, int b) {return(a + randxor() % (b - a));} using innt = int16_t; //variable constexpr int TIME_LIMIT = 10000; constexpr int N = 50; int A[N][N]; constexpr int BEAM_WIDETH = 1000; struct CapArr { int sz = 0; array<mint, N> arr; CapArr() {} mint operator[](int i)const{return arr[i];} void push(const mint& x){ arr[sz] = x; sz++; } void pop(){sz--;} void resize(int x){sz = x;} void clear(){sz = 0;} void shuffle(){ rep(i, sz - 1) swap(arr[i], arr[i + randint(0, sz - i)]); } const mint back(){return arr[sz - 1];} const int size(){return sz;} }; struct State { ll score = 0; int hash = 0; vc<mint> na; friend bool operator>(const State& u, const State& v){return u.score > v.score;} friend bool operator<(const State& u, const State& v){return u.score < v.score;} }; struct Solver { const int TURN = 49; State best_state; priority_queue<State> beam_log[N]; void input(){ if (DEBUGMODE){ ifstream in(inputfile); cin.rdbuf(in.rdbuf()); int a; cin >> a; rep(i, N) rep(j, i + 1) cin >> A[i][j]; }else{ int a; cin >> a; rep(i, N) rep(j, i + 1) cin >> A[i][j]; } } void init(){ best_state.score = INF; } void output(){ wrt.open(outputfile, ios::out); if (DEBUGMODE){ cout << best_state.score / 1000 << endl; }else{ rep(i, N) cout << best_state.na[i].val << " "; cout << endl; } wrt.close(); } void transition(State &s, int turn){ for (int dif = -4e7; dif <= 4e7; dif += 1e6){ State ns = s; ns.na[0] = mint(A[turn][0] + dif); ns.score = max((ll)abs(dif), s.score / 1000); srep(j, 1, turn){ ns.na[j] = s.na[j - 1] - ns.na[j - 1]; ns.score = max(ns.score, (ll)min((A[turn][j] - ns.na[j]).val, mod - (A[turn][j] - ns.na[j]).val)); } ns.na.push_back(s.na[turn - 1] - ns.na[turn - 1]); ns.score = max(ns.score, (ll)min((A[turn][turn] - ns.na[turn]).val, mod - (A[turn][turn] - ns.na[turn]).val)); ns.score = ns.score * 1000 + randint(0, 1000);//tayouka if (turn == N - 1 && best_state.score > ns.score) best_state = ns; else if (len(beam_log[turn]) < BEAM_WIDETH) beam_log[turn].push(ns); else if (beam_log[turn].top().score > ns.score){ beam_log[turn].pop(); beam_log[turn].push(ns); } } } void beam(){ State st; st.na.push_back(0); for (int dif = -4e7; dif <= 4e7; dif += 1e6){ st.na[0] = mint(A[0][0] + dif); st.score = abs(dif) * 1000 + randint(0, 1000); beam_log[0].push(st); } rep(turn, TURN){ while (!beam_log[turn].empty()){ auto s = beam_log[turn].top(); transition(s, turn + 1); beam_log[turn].pop(); } } } void solve(){ input(); init(); beam(); output(); } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); Solver solver; solver.solve(); return 0; }