結果
| 問題 |
No.5021 Addition Pyramid
|
| コンテスト | |
| ユーザー |
 momohara
|
| 提出日時 | 2025-02-25 22:38:04 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,885 ms / 2,000 ms |
| コード長 | 6,000 bytes |
| コンパイル時間 | 6,990 ms |
| コンパイル使用メモリ | 335,212 KB |
| 実行使用メモリ | 6,820 KB |
| スコア | 40,517,427 |
| 最終ジャッジ日時 | 2025-02-25 22:39:51 |
| 合計ジャッジ時間 | 101,575 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge7 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
// constexpr long long MOD = (ll)1e9 + 7;
constexpr long long MOD = 998244353LL;
static const ld pi = 3.141592653589793L;
template <class T>
inline bool chmin(T &a, T b) {
if(a > b) {
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T &a, T b) {
if(a < b) {
a = b;
return true;
}
return false;
}
constexpr double TL = 1.5;
struct Timer {
chrono::system_clock::time_point start, last_updated;
Timer() {
start = chrono::system_clock::now();
last_updated = chrono::system_clock::now();
}
void reset() {
start = chrono::system_clock::now();
}
void update() {
last_updated = chrono::system_clock::now();
}
double getTime() {
auto now = chrono::system_clock::now();
return chrono::duration<double>(now - start).count();
}
double should_finish_search1() {
return getTime() > TL;
}
bool should_reset() {
auto now = chrono::system_clock::now();
return chrono::duration<double>(now - last_updated).count() > 1.0 ||
chrono::duration<double>(now - start).count() > TL;
}
};
Timer timer;
struct Xor128 {
unsigned x, y, z, w;
Xor128() : x(123456789), y(362436069), z(521288629), w(88675123){};
inline unsigned xor128() {
unsigned t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int nextInt(int x, int y) {
return xor128() % (y - x) + x;
}
double nextDouble(double a, double b) {
return (double)(xor128() & 0xffff) / 0xffff * (b - a) + a;
}
};
auto rnd = Xor128();
void solve() {
ll n;
cin >> n;
using mint = modint;
modint::set_mod(100000000);
vvec<mint> a(n);
REP(i, n) {
a[i] = vector(i + 1, mint(0));
REP(j, i + 1) {
ll aa;
cin >> aa;
a[i][j] = aa;
}
}
// 各ますの影響度が入る
vec<vvec<mint>> d(n);
REP(s, n) {
vvec<mint> dd(n);
dd[n - 1].resize(n, 0);
dd[n - 1][s] = 1;
REP2(i, n - 1) {
dd[i].resize(i + 1, 0);
REP(j, i + 1) {
dd[i][j] = dd[i + 1][j] + dd[i + 1][j + 1];
}
}
d[s] = dd;
}
vvec<mint> b(n);
b[n - 1] = a[n - 1];
REP2(i, n - 1) {
b[i].resize(i + 1, 0);
REP(j, i + 1) {
b[i][j] = b[i + 1][j] + b[i + 1][j + 1];
}
}
vvec<bool> ignore(n, vec<bool>(n, false));
REP(_, 100000) {
ll ma = -1;
ll pma = -1;
int mai = -1;
int maj = -1;
REP(i, n) {
REP(j, i + 1) {
ll diff = min((b[i][j] - a[i][j]).val(), (a[i][j] - b[i][j]).val());
chmax(ma, diff);
if(!ignore[i][j] and chmax(pma, diff)) {
mai = i;
maj = j;
}
}
}
if(mai != -1) {
int i = mai;
int j = maj;
ll diff = (a[i][j] - b[i][j]).val();
ll nma = -1;
REP(s, n) {
if(d[s][i][j] != 1)
continue;
REP(i, n) {
REP(j, i + 1) {
b[i][j] += d[s][i][j] * diff;
ll ndiff = min((b[i][j] - a[i][j]).val(), (a[i][j] - b[i][j]).val());
chmax(nma, ndiff);
}
}
if(nma < ma)
break;
// rollback
nma = -1;
REP(i, n) {
REP(j, i + 1) {
b[i][j] -= d[s][i][j] * diff;
}
}
}
if(nma == -1) {
// 改善できる手がない
ignore[i][j] = true;
}
// cerr << nma << endl;
}
}
REP(_, 100000) {
int s = rnd.nextInt(0, n);
int t = rnd.nextInt(0, 1e8);
ll ma = -1;
ll nma = -1;
REP(i, n) {
REP(j, i + 1) {
ll diff = min((b[i][j] - a[i][j]).val(), (a[i][j] - b[i][j]).val());
chmax(ma, diff);
b[i][j] += d[s][i][j] * t;
ll ndiff = min((b[i][j] - a[i][j]).val(), (a[i][j] - b[i][j]).val());
chmax(nma, ndiff);
}
}
if(nma < ma)
continue;
// rollback
REP(i, n) {
REP(j, i + 1) {
b[i][j] -= d[s][i][j] * t;
}
}
}
vec<mint> c = b[n - 1];
for(auto cc : c) {
cout << cc.val() << " ";
}
cout << en;
#if !defined(ONLINE_JUDGE)
// ローカル用出力
ll x = 0;
REP(i, n) {
REP(j, i + 1) {
ll diff = min((b[i][j] - a[i][j]).val(), (a[i][j] - b[i][j]).val());
chmax(x, diff);
}
}
ll score = 5e7 - x;
cerr << score << en;
#endif
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cout << fixed << setprecision(10);
// ll t;
// cin >> t;
// REP(i, t - 1) {
// solve();
// }
solve();
return 0;
}