結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー tombo_
提出日時 2025-04-27 07:30:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,853 ms / 2,000 ms
コード長 4,020 bytes
コンパイル時間 2,443 ms
コンパイル使用メモリ 204,796 KB
実行使用メモリ 7,848 KB
スコア 3,197,430
最終ジャッジ日時 2025-04-27 07:32:34
合計ジャッジ時間 99,103 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define REP(i, l, r) rep(i, l, r+1)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
struct Edge {
  int to; ll w;
};
using Graph = vector<vector<int> >;
//using Graph = vector<vector<Edge> >;
const ll INF = 2e18;
//const int INF = 2e9;
template<class T> using vc = vector<T>;
template<class T> using vv = vector<vector<T> >;
template<class T> using vvv = vector<vector<vector<T> > >;
template<class T> using pq = priority_queue<T>;
template<class T> using pq_g = priority_queue<T, vc<T>, greater<T> >;
template<class T> istream& operator>>(istream& i, vc<T>& v) { rep(j, 0, v.size()) i>>v[j]; return i; }
template<class T> ostream& operator<<(ostream& o, vc<T>& v) { rep(j, 0, v.size()) o<<v[j]<<" "; return o; }
template<class T> bool chmin(T& a, T b) {
  if(a > b) {
      a = b;
      return true;
  }
  return false;
}
template<class T> bool chmax(T& a, T b) {
  if(a < b) {
      a = b;
      return true;
  }
  return false;
}

class Timer{
    chrono::system_clock::time_point start;
    public:
        Timer() : start(chrono::system_clock::now()) {}

        double count(){
            chrono::duration<double> Time_ = chrono::system_clock::now() - start;
            return Time_.count();
        }

        bool is_under(double x){
            return (this -> count()) < x;
        }
};
// std::uniform_int_distributionを利用した一様乱数生成クラス
class Random_Gen{
    random_device seed_gen;
    mt19937 engine;
    uniform_int_distribution<int64_t> dist;
    public:
        // Constructor [l,r]で生成する値の範囲を指定
        Random_Gen() : engine(seed_gen()) {}
        Random_Gen(int64_t l, int64_t r) : engine(seed_gen()), dist(l,r) {}

        // 現在の生成する値の範囲をstd::pairで返す
        pair<int64_t,int64_t> get_range(){
            return make_pair(dist.min(),dist.max());
        }
        // 生成する値の範囲を[l,r]に変更する
        void set_range(int64_t l, int64_t r){
            uniform_int_distribution<int64_t>::param_type Param(l,r);
            dist.param(Param);
        }
        // [l,r]内の一様分布の整数を返す
        int64_t gen(){
            return dist(engine);
        }
        int64_t operator()(){ return gen(); }
};
ll mod = 100000000;
ll score(const vv<ll>& a, const vc<ll>& solv) {
  int N = a.size();
  vv<ll> res(N);
  rep(i, 0, N) res[i].resize(i+1);
  rep(i, 0, N) res[N-1][i] = solv[i];
  
  ll score = 0;
  for(int i = N-2; i >= 0; i--) {
    rep(j, 0, i+1) {
      res[i][j] = (res[i+1][j] + res[i+1][j+1]) % mod;
    }
  }
  rep(i, 0, N) rep(j, 0, i+1) score += min(abs(a[i][j]-res[i][j]), mod-abs(a[i][j]-res[i][j]));
  return score;
}

int main() {
  // 高速化
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // 小数点の出力桁数を指定
  cout << fixed << setprecision(10);
  // メイン
  int N;
  cin >> N;
  vv<ll> a(N);
  rep(i, 0, N) a[i].resize(i+1);
  rep(i, 0, N) cin >> a[i];

  vc<ll> solv(N);
  rep(i, 0, N) solv[i] = a[N-1][i];

  Timer timer;
  Random_Gen random(0, N), randnum(0, 100000000);
  ll curscore = score(a, solv);
  while(true) {
    if(!timer.is_under(1.85)) break;
    {
    int b, c;
    b = random(), c = random();
    vc<ll> nsolve(solv);
    swap(nsolve[b], nsolve[c]);
    ll s = score(a, nsolve);
    if(s < curscore) {
      solv = nsolve;
      curscore = s;
    }
    }
    {
    int p = random();
    int d = randnum();
    vc<ll> nsolve(solv);
    nsolve[p] = d;
    ll s = score(a, nsolve);
    if(s < curscore) {
      solv = nsolve;
      curscore = s;
    }
    }
  }

  rep(i, 0, N) cout << solv[i] << endl;

  return 0;
}
0