結果
問題 | No.1717 Levi-Civita Triangle |
ユーザー |
![]() |
提出日時 | 2021-10-22 21:47:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 2,063 bytes |
コンパイル時間 | 3,637 ms |
コンパイル使用メモリ | 183,316 KB |
最終ジャッジ日時 | 2025-01-25 03:27:29 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; int main() { int n; cin>>n; int a[200020]; for(int i=0; i<2*n+1; i++) cin>>a[i]; int a1[2][4]={{0,2,1,2},{0,1,2,1}}; bool b1=1, b2=1; for(int i=1; i<2*n+1; i++){ int x=(a[i]-a[0]+3)%3; if(x!=a1[n%2][i%4]){ b1=0; } if(x!=a1[(n%2)^1][i%4]){ b2=0; } } if(b1)cout<<1<<endl; else if(b2)cout<<2<<endl; else cout<<0<<endl; return 0; set<vector<int>> st; auto dfs=[&](auto dfs, vector<int> &v)->void{ if(v.size()==2*n+1){ auto w=v; for(int i=0; i<n; i++){ vector<int> w1; for(int j=1; j<(int)w.size()-1; j++){ if((w[j]-w[j-1]+3)%3==1 && (w[j+1]-w[j]+3)%3==1){ w1.push_back(1); }else if((w[j]-w[j-1]+3)%3==2 && (w[j+1]-w[j]+3)%3==2){ w1.push_back(2); }else{ w1.push_back(0); } } swap(w, w1); } if(w[0]==2){ for(int i=0; i<2*n+1; i++) cout<<v[i]<<" "; cout<<endl; st.insert(v); } return; } for(int i=0; i<3; i++){ v.push_back(i); dfs(dfs, v); v.pop_back(); } }; vector<int> v0; dfs(dfs, v0); cout<<st.size()<<endl; return 0; }