結果

問題 No.675 ドットちゃんたち
コンテスト
ユーザー ama_nuko
提出日時 2018-07-13 16:39:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 288 ms / 2,000 ms
コード長 1,909 bytes
コンパイル時間 1,423 ms
コンパイル使用メモリ 106,412 KB
実行使用メモリ 24,320 KB
最終ジャッジ日時 2024-10-08 14:06:27
合計ジャッジ時間 5,206 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

typedef vector<int> Vec;
typedef vector<Vec> Mat;

Mat multi(Mat a, Mat b){
    Mat c(a.size(), Vec(b[0].size()));

    rep(i, (int)a.size()){
        rep(j, (int)b[0].size()){
            rep(k, (int)b.size()){
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

Vec multi(Mat a, Vec b){
    Vec c(a.size());

    rep(i, (int)a.size()){
        rep(j, (int)b.size()){
            c[i] += a[i][j] * b[j];
        }
    }
    return c;
}

signed main(){
    int n, x, y;
    cin >> n >> x >> y;

    vector<int> cmd(n), d(n);
    rep(i, n){
        cin >> cmd[i];
        if(cmd[i] != 3){
            cin >> d[i];
        }
    }

    //vector<int> px(n+1), py(n+1);
    vector<Mat> mat(n+1, Mat(3, Vec(3)));
    mat[n][0][0] = 1;
    mat[n][1][1] = 1;
    mat[n][2][2] = 1;
    for(int i = n-1; i >= 0; i--){
        Mat m(3, Vec(3));

        if(cmd[i] == 1){
            m[0][0] = 1;
            m[1][1] = 1;
            m[2][2] = 1;
            m[0][2] = d[i];
        }
        if(cmd[i] == 2){
            m[0][0] = 1;
            m[1][1] = 1;
            m[2][2] = 1;
            m[1][2] = d[i];
        }
        if(cmd[i] == 3){
            m[0][1] = 1;
            m[1][0] = -1;
            m[2][2] = 1;
        }
        mat[i] = multi(mat[i+1], m);
    }

    Vec v(3);
    v[0] = x;
    v[1] = y;
    v[2] = 1;
    rep(i, n){
        Vec ans = multi(mat[i], v);
        cout << ans[0] << " " << ans[1] << endl;
    }

    return 0;
}
0