結果

問題 No.1935 Water Simulation
ユーザー orange navleorange navle
提出日時 2022-05-13 22:54:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,307 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 185,340 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-22 03:08:48
合計ジャッジ時間 3,182 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;

#define rep(i,n) for(LL i=0;i<(n);i++)

template <class T>
void output(vector<T> &data){

    rep(i,data.size()){
        cout << data.at(i) << " ";
    }
    cout << endl;

}

template<>
void output(vector<string> &data){
 
    rep(i,data.size()){
        cout << data.at(i) << endl;
    }
 
}

template <class T>
void output(vector<vector<T>> &data){

    rep(i,data.size()){

        rep(j,data.at(i).size()){
            cout << data.at(i).at(j) << " ";
        }

        cout << endl;

    }

}

template <>
void output(vector<vector<bool>> &data){

    rep(i,data.size()){

        rep(j,data.at(i).size()){

            if(data.at(i).at(j)){
                cout << "*";
            }
            else{
                cout << "-";
            }

        }

        cout << endl;

    }

}

template<class T>
void input(vector<T> &data,LL n){
    
    rep(i,n){
        LL a; cin >> a;
        data.push_back(a);
    }

}

template<>
void input(vector<string> &data,LL n){

    rep(i,n){
        string s; cin >> s;
        data.push_back(s);
    }

}

template<class T>
void input(vector<vector<T>> &data,LL h, LL w){

    rep(i,h){
        vector<T> add;

        rep(j,w){
            T a; cin >> a;
            add.push_back(a);
        }

        data.push_back(add);

    }

}

int main(){
    int n;
    vector<int> v;
    vector<int> water;

    input(v,4);
    cin >> n;

    rep(i,v.size()){
        if(i == 0){
            water.push_back(v.at(i));
        }
        else{
            water.push_back(0);
        }
    }

    set<vector<int>> check;
    check.insert(water);

    vector<vector<int>> history;
    vector<int> last;

    int prev_size = check.size();
    int next_size = check.size();

    do{
        prev_size = check.size();
        history.push_back(water);

        rep(i,v.size()){
            int from_pos = i;
            int to_pos = (i+1)%v.size();

            int pur = std::min(water.at(from_pos),v.at(to_pos) - water.at(to_pos));

            water.at(from_pos) -= pur;
            water.at(to_pos) += pur;

        }

        check.insert(water);
        last = water;

        next_size = check.size();
    }while(prev_size != next_size);

    int start_pos = -1; // loop start

    rep(i,history.size()){

        if(history.at(i) == last){
            start_pos = i;
            break;
        }

    }

    int prev = start_pos;
    int need = prev * 4;
    int result_pos = start_pos;
    int reset_pos = start_pos;

    if(n >= need){
        n -= need;
    }
    else{
        result_pos = 0;
        reset_pos = 0;
    }

    int loop_size = history.size() - start_pos;
    int all = loop_size * 4;
    n %= all;

    vector<int> ans;

    while(true){

        if(n < 4){
            ans = history.at(result_pos);
            break;
        }

        n %= 4;
        result_pos++;

        if(result_pos == history.size()){
            result_pos = reset_pos;
        }

    }

    rep(i,n){
        int from_pos = i;
        int to_pos = (i+1)%v.size();
        int pur = std::min(ans.at(from_pos),v.at(to_pos) - ans.at(to_pos));

        ans.at(from_pos) -= pur;
        ans.at(to_pos) += pur;
    }

    output(ans);

    return 0;
}

/*
9 5 7 4 0
*/
0