結果

問題 No.2148 ひとりUNO
コンテスト
ユーザー tnakao0123
提出日時 2022-12-09 10:39:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 2,212 bytes
コンパイル時間 496 ms
コンパイル使用メモリ 55,504 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 18:35:04
合計ジャッジ時間 1,919 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2148.cc:  No.2148 ひとりUNO - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
 
using namespace std;

/* constant */

const int MAX_N = 200000;
enum { B, G, R };

/* typedef */

typedef pair<int,int> pii;

/* global variables */

int e0[3][3], e1[3][3], cls[3];
pii ps[MAX_N];

/* subroutines */

inline int c2i(char c) {
  return (c == 'B') ? B : (c == 'G') ? G : (c == 'R') ? R : -1;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < 3; i++) fill(e0[i], e0[i] + 3, 0);
    for (int i = 0; i < 3; i++) fill(e1[i], e1[i] + 3, 0);
    fill(cls, cls + 3, 0);
    int cn = 0;

    for (int i = 0; i < n; i++) {
      char s[4];
      int di;
      scanf("%s%d", s, &di);
      int ci = c2i(s[0]);
      ps[i] = pii(di, ci);
      if (! cls[ci]) cn++;
      cls[ci]++;
    }
    sort(ps, ps + n);

    for (int i = 0; i < n;) {
      int i0 = i;
      while (i < n && ps[i0].first == ps[i].first) i++;

      if (i - i0 > 1)
	for (int j0 = i0; j0 < i; j0++)
	  for (int j1 = j0 + 1; j1 < i; j1++) {
	    int c0 = ps[j0].second, c1 = ps[j1].second;
	    if (! e0[c0][c1])
	      e0[c0][c1] = e0[c1][c0] = ps[i0].first;
	    else if (! e1[c0][c1])
	      e1[c0][c1] = e1[c1][c0] = ps[i0].first;
	  }
    }

    //for (int i = 0; i < 3; i++) {
    //for (int j = 0; j < 3; j++) printf("%d,%d ", e0[i][j], e1[i][j]);
    //putchar('\n');
    //}

    bool ok = false;
    if (cn == 1)
      ok = true;
    else if (cn == 2) {
      int c0 = -1, c1 = -1;
      for (int i = 0; i < 3; i++)
	if (cls[i]) {
	  if (c0 < 0) c0 = i;
	  else c1 = i;
	}

      ok = (e0[c0][c1] > 0);
    }
    else {
      for (int c0 = 0; ! ok && c0 < 3; c0++) {
	int c1 = (c0 + 1) % 3, c2 = (c0 + 2) % 3;
	int e01 = e0[c0][c1], e11 = e1[c0][c1];
	int e02 = e0[c0][c2], e12 = e1[c0][c2];
	if (cls[c0] == 1 && e01 && e02)
	  ok = true;
	else if (cls[c0] > 1 &&
		 ((e01 && e02 && e01 != e02) ||
		  (e01 && e12 && e01 != e12) ||
		  (e11 && e02 && e11 != e02) ||
		  (e11 && e12 && e11 != e12)))
	  ok = true;
      }
    }

    if (ok) puts("YES");
    else puts("NO");
  }
  return 0;
}
0