結果

問題 No.1935 Water Simulation
ユーザー miscalcmiscalc
提出日時 2023-11-20 20:55:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,167 bytes
コンパイル時間 4,496 ms
コンパイル使用メモリ 268,740 KB
実行使用メモリ 6,548 KB
最終ジャッジ日時 2023-11-20 20:55:11
合計ジャッジ時間 6,098 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 AC 2 ms
6,548 KB
testcase_02 AC 2 ms
6,548 KB
testcase_03 AC 1 ms
6,548 KB
testcase_04 AC 2 ms
6,548 KB
testcase_05 AC 2 ms
6,548 KB
testcase_06 AC 2 ms
6,548 KB
testcase_07 AC 2 ms
6,548 KB
testcase_08 AC 2 ms
6,548 KB
testcase_09 AC 2 ms
6,548 KB
testcase_10 AC 2 ms
6,548 KB
testcase_11 AC 1 ms
6,548 KB
testcase_12 AC 2 ms
6,548 KB
testcase_13 AC 2 ms
6,548 KB
testcase_14 AC 2 ms
6,548 KB
testcase_15 AC 1 ms
6,548 KB
testcase_16 AC 2 ms
6,548 KB
testcase_17 AC 2 ms
6,548 KB
testcase_18 AC 2 ms
6,548 KB
testcase_19 AC 2 ms
6,548 KB
testcase_20 AC 2 ms
6,548 KB
testcase_21 AC 2 ms
6,548 KB
testcase_22 AC 1 ms
6,548 KB
testcase_23 AC 2 ms
6,548 KB
testcase_24 AC 2 ms
6,548 KB
testcase_25 AC 2 ms
6,548 KB
testcase_26 AC 2 ms
6,548 KB
testcase_27 AC 2 ms
6,548 KB
testcase_28 AC 1 ms
6,548 KB
testcase_29 AC 1 ms
6,548 KB
testcase_30 AC 2 ms
6,548 KB
testcase_31 AC 2 ms
6,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using tlll = tuple<ll, ll, ll>;
constexpr ll INF = 1LL << 60;
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;}
ll safemod(ll A, ll M) {ll res = A % M; if (res < 0) res += M; return res;}
ll divfloor(ll A, ll B) {if (B < 0) A = -A, B = -B; return (A - safemod(A, B)) / B;}
ll divceil(ll A, ll B) {if (B < 0) A = -A, B = -B; return divfloor(A + B - 1, B);}
ll pow_ll(ll A, ll B) {if (A == 0 || A == 1) {return A;} if (A == -1) {return B & 1 ? -1 : 1;} ll res = 1; for (int i = 0; i < B; i++) {res *= A;} return res;}
ll mul_limited(ll A, ll B, ll M = INF) { return B == 0 ? 0 : A > M / B ? M : A * B; }
ll pow_limited(ll A, ll B, ll M = INF) { if (A == 0 || A == 1) {return A;} ll res = 1; for (int i = 0; i < B; i++) {if (res > M / A) return M; res *= A;} return res;}
template<class T> void unique(vector<T> &V) {V.erase(unique(V.begin(), V.end()), V.end());}
template<class T> void sortunique(vector<T> &V) {sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end());}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)
template<class T> void printvec(const vector<T> &V) {int _n = V.size(); for (int i = 0; i < _n; i++) cout << V[i] << (i == _n - 1 ? "" : " ");cout << '\n';}
template<class T> void printvect(const vector<T> &V) {for (auto v : V) cout << v << '\n';}
template<class T> void printvec2(const vector<vector<T>> &V) {for (auto &v : V) printvec(v);}
//*
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;
//*/

/*
x[0] = start, x[i+1] = next_index(x[i]) の漸化式で定まるインデックス列に対して
get(x[0]) op … op get(x[K-1]) を求める (K はクエリで渡される)
Index: x_i の型
Data: 求める値の型、モノイド
  op: 結合則を満たす演算
  e: 単位元
  power(b, t) = b^t = b op … op b (t 回)
計算量: 前計算 O(周期)、クエリ O(1)
*/
template <typename Index, typename Data, Index (*next_index)(Index), Data (*get)(Index), Data (*op)(Data, Data), Data (*e)(), Data (*power)(Data, ll)>
struct Period
{
private:
  vector<Data> dat, prod_head, prod_tail;
  int lambda, mu;
  Data head, tail;

public:
  Period(Index start)
  {
    Index a = start, b = start;
    do
    {
      dat.emplace_back(get(a));
      a = next_index(a);
      b = next_index(next_index(b));
    } while (a != b);
    mu = dat.size();
    Index c = start;
    while (a != c)
    {
      dat.emplace_back(get(a));
      a = next_index(a);
      c = next_index(c);
    }
    lambda = (int)dat.size() - mu;

    prod_head.resize((int)dat.size() + 1);
    prod_tail.resize((int)dat.size() + 1);
    prod_head[0] = e(), prod_tail[lambda] = e();
    for (int i = 1; i < (int)prod_head.size(); i++)
      prod_head[i] = op(prod_head[i - 1], dat[i - 1]);
    for (int i = lambda + 1; i < (int)prod_tail.size(); i++)
      prod_tail[i] = op(prod_tail[i - 1], dat[i - 1]);

    head = prod_head[lambda];
    tail = prod_tail[lambda + mu];
  }

  Data query(ll k)
  {
    if (k <= (int)dat.size())
      return prod_head[k];
    
    Data mid = prod_tail[lambda + (k - lambda) % mu];
    return op(op(head, power(tail, (k - lambda) / mu)), mid);
  }
};

array<ll, 4> V;
using state = pair<ll, array<ll, 4>>;
state next_index(state s)
{
  auto [i, v] = s;
  ll j = (i + 1) % 4;
  ll k = min(v.at(i), V.at(j) - v.at(j));
  v.at(i) -= k, v.at(j) += k;
  return {j, v};
}
state get(state s) { return s; }
state e() { return {-1, {{-1, -1, -1, -1}}}; }
state op(state a, state b) { return b == e() ? a : b; }
state power(state a, ll t) { return a; }

int main()
{
  for (ll i = 0; i < 4; i++)
  {
    cin >> V.at(i);
  }
  ll N;
  cin >> N;

  Period<state, state, next_index, get, op, e, power> pe({0, {{V.at(0), 0, 0, 0}}});
  auto ans = pe.query(N + 1).second;
  for (ll i = 0; i < 4; i++)
  {
    cout << ans.at(i) << (i == 3 ? '\n' : ' ');
  }
}
0