結果

問題 No.675 ドットちゃんたち
ユーザー 0w10w1
提出日時 2018-04-15 02:53:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 244 ms / 2,000 ms
コード長 1,582 bytes
コンパイル時間 2,203 ms
コンパイル使用メモリ 211,736 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 22:42:07
合計ジャッジ時間 5,426 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 227 ms
5,376 KB
testcase_06 AC 241 ms
5,376 KB
testcase_07 AC 219 ms
5,376 KB
testcase_08 AC 234 ms
5,376 KB
testcase_09 AC 237 ms
5,376 KB
testcase_10 AC 244 ms
5,376 KB
testcase_11 AC 233 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;

template <typename T>
using vec = vector<T>;
using mat = vec<vec<int>>;

mat operator *(mat a, mat b) {
  mat c = mat(a.size(), vec<int>(b[0].size()));
  for (int i = 0; i < a.size(); ++i) {
    for (int k = 0; k < b.size(); ++k) {
      for (int j = 0; j < b[0].size(); ++j) {
        c[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return c;
}

signed main() {
  ios::sync_with_stdio(false);

  int N, Px, Py;
  cin >> N >> Px >> Py;

  mat x = mat(3, vec<int>(1));
  x[0][0] = Px;
  x[1][0] = Py;
  x[2][0] = 1;

  mat prod_t = mat(3, vec<int>(3));
  for (int i = 0; i < 3; ++i) {
    prod_t[i][i] = 1;
  }

  vector<int> OP;
  for (int i = 0; i < N; ++i) {
    int op;
    cin >> op;
    if (op < 3) {
      int u;
      cin >> u;
      OP.emplace_back(u);
    }
    OP.emplace_back(op);
  }
  reverse(OP.begin(), OP.end());

  vector<pair<int, int>> ans(N);
  for (int i = 0, ptr = 0; i < N; ++i) {
    int op = OP[ptr++];
    mat t = mat(3, vec<int>(3));
    if (op == 1) {
      int Dx = OP[ptr++];
      for (int j = 0; j < 3; ++j) {
        t[j][j] = 1;
      }
      t[0][2] = Dx;
    } else if (op == 2) {
      int Dy = OP[ptr++];
      for (int j = 0; j < 3; ++j) {
        t[j][j] = 1;
      }
      t[1][2] = Dy;
    } else {
      t[0][1] = 1;
      t[1][0] = -1;
      t[2][2] = 1;
    }
    prod_t = prod_t * t;
    mat res = prod_t * x;
    ans[N - 1 - i] = make_pair(res[0][0], res[1][0]);
  }

  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i].first << ' ' << ans[i].second << endl;
  }

  return 0;
}
0