結果
問題 | No.197 手品 |
ユーザー |
|
提出日時 | 2022-09-28 17:33:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,478 bytes |
コンパイル時間 | 2,165 ms |
コンパイル使用メモリ | 203,572 KB |
最終ジャッジ日時 | 2025-02-07 17:57:26 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; using mat = vector<vector<int>>; mat matmul(mat A, mat B) { int n = int(A.size()); vector<vector<int>> ans(n, vector<int>(n, 0)); for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { ans[i][j] |= A[i][k] & B[k][j]; } } } return ans; } mat matpow(mat A, ll b) { int n = int(A.size()); vector<vector<int>> ans(n, vector<int>(n, 0)); rep(i,n) ans[i][i] = 1; while(b > 0) { if(b % 2 == 1) ans = matmul(ans, A); A = matmul(A, A); b /= 2; } return ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int K = (1 << 3); vector<vector<int>> A(K, vector<int>(K, 0)); rep(S,K) { vector<int> v(3); rep(i,3) v[i] = !!(S & (1 << i)); swap(v[0], v[1]); int T = 0; rep(i,3) if(v[i]) T |= (1 << i); A[S][T] = 1; swap(v[1], v[0]); swap(v[1], v[2]); T = 0; rep(i,3) if(v[i]) T |= (1 << i); A[S][T] = 1; swap(v[1], v[2]); } string S, T; int N; cin >> S >> N >> T; A = matpow(A, N); auto f = [](string X) { int res = 0; rep(i,3) if(X[i] == 'o') res |= (1 << i); return res; }; cout << (A[f(S)][f(T)] ? "FAILURE" : "SUCCESS") << endl; }