結果

問題 No.675 ドットちゃんたち
ユーザー Toshiyuki OikeToshiyuki Oike
提出日時 2018-04-19 15:11:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 294 ms / 2,000 ms
コード長 2,367 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 70,056 KB
実行使用メモリ 23,808 KB
最終ジャッジ日時 2024-06-27 04:46:26
合計ジャッジ時間 4,014 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "iostream"
#include "vector"

#define MAX_N 100005

using namespace std;

typedef long long llint;

int N;
llint Px, Py;

pair<int, int> command[MAX_N];
vector<vector<llint> > dots[MAX_N];

void printMat(vector<vector<llint> > a) {
    
    for(int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[0].size(); j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}

vector<vector<llint> > mul(vector<vector<llint> > a, vector<vector<llint> > b) {
    vector<vector<llint> > res(a.size(), vector<llint>(b[0].size(), 0));

    for(int i = 0; i < a.size(); i++) {
        for(int j = 0; j < b[0].size(); j++) {
            for(int k = 0; k < b.size(); k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    return res;
}

int main() {

    cin >> N >> Px >> Py;

    vector<vector <llint> > fp(3, vector<llint>(1, 0));
    fp[0][0] = Px;
    fp[1][0] = Py;
    fp[2][0] = 1;

    for (int i = 0; i < N; i++) {
        cin >> command[i].first;

        if (command[i].first == 1 || command[i].first == 2) {
            cin >> command[i].second;
        } else {
            command[i].second = 0;
        }
    }

    vector<vector <llint> > m(3, vector<llint>(3, 0));
    m[0][0] = 1;
    m[1][1] = 1;
    m[2][2] = 1;
    for (int i = N - 1; i >= 0; i--) { 
        if (command[i].first == 1) {
            vector<vector <llint> > x(3, vector<llint>(3, 0));

            x[0][0] = 1;
            x[1][1] = 1;
            x[2][2] = 1;
            x[0][2] = command[i].second;

            m = mul(m, x);
        } else if (command[i].first == 2) {
            vector<vector <llint> > y(3, vector<llint>(3, 0));

            y[0][0] = 1;
            y[1][1] = 1;
            y[2][2] = 1;
            y[1][2] = command[i].second;

            m = mul(m, y);
        } else {
            vector<vector <llint> > lotate(3, vector<llint>(3, 0));

            lotate[0][1] = 1;
            lotate[1][0] = -1;
            lotate[2][2] = 1;

            m = mul(m, lotate);
        }
        
        dots[i] = mul(m, fp);
        // vector<vector<llint> > dot = mul(m, fp);
        // cout << dot[0][0] << " " << dot[1][0] << endl;
    }

    for (int i = 0; i < N; i++) {
        // cout << endl;
        // printMat(dots[i]);
        cout << dots[i][0][0] << " " << dots[i][1][0]<< endl;
    }
}
0