結果

問題 No.1935 Water Simulation
ユーザー orange navleorange navle
提出日時 2022-05-13 22:55:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,318 bytes
コンパイル時間 1,928 ms
コンパイル使用メモリ 185,988 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-22 03:10:35
合計ジャッジ時間 2,903 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;
        int loop_size = history.size() - start_pos;
        int all = loop_size * 4;
        n %= all;
    }
    else{
        result_pos = 0;
        reset_pos = 0;
    }

    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