結果
問題 |
No.2148 ひとりUNO
|
ユーザー |
|
提出日時 | 2023-07-10 22:45:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 2,732 bytes |
コンパイル時間 | 965 ms |
コンパイル使用メモリ | 109,688 KB |
最終ジャッジ日時 | 2025-02-15 09:38:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 39 |
ソースコード
/* 1が三食 R 1 2 G 1 3 B 1 5 */ #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<int,int> P; typedef pair<int,P> PP; const ll MOD=998244353; const double PI=acos(-1); bool solve(){ int N; cin>>N; //set<int> rst,bst,gst; vector<set<int>> st(3); int match=0; for(int i=0;i<N;i++){ char c; int d; cin>>c>>d; if(c=='R'){ st[0].insert(d); //rst.insert(d); match|=(1<<0); }else if(c=='G'){ st[1].insert(d); // gst.insert(d); match|=(1<<1); }else if(c=='B'){ st[2].insert(d); // bst.insert(d); match|=(1<<2); } } if(__builtin_popcount(match)==1){ //そもそもカードが一種類しかない //必ずtrue return true; }else if(__builtin_popcount(match)==2){ //カードが2種類しかない vector<int> cnt(N+1,0); for(int i=0;i<3;i++){ for(int v:st[i]){ cnt[v]++; if(cnt[v]==2){ //2回出現すればOK return true; } } } return false; } //3色ある場合 vector<int> p={0,1,2}; do{ //st[1]に相当するカード->st[0]に相当するカード->st[2]に相当するカード /* st[1],st[0]に相当するカードがあるならflag1=true カード集合をc1 st[0],st[1]に相当するカードがあるならflag2=true カード集合をc2とする flag1とflag2が両方trueのとき st[0]が1種類しかないならtrue */ bool flag1=false,flag2=false; set<int> c1,c2; for(int v:st[p[0]]){ if(st[p[1]].count(v)){ flag1=true; c1.insert(v); } if(st[p[2]].count(v)){ flag2=true; c2.insert(v); } } if(!flag1 || !flag2) continue; if(c1!=c2){ return true; } if(c1==c2){ if(c1.size()>1) return true; //c1.size()==1 if(st[p[0]].size()==1) return true; } }while(next_permutation(p.begin(),p.end())); return false; } int main(){ int T; cin>>T; for(int t=0;t<T;t++){ bool ans=solve(); cout<<(ans?"YES":"NO")<<endl; } }