ferinの競プロ帳

競プロについてのメモ

Codeforces Round #444 (Div. 2) C. Solution for Cube

問題ページ
Problem - 887C - Codeforces

概要

2×2×2の立方体のルービックキューブが入力で与えられる。一回回転することで色が揃えられるなら"YES"、揃わなければ"NO"を出力する。

解法

回転のパターンは6パターンで反転で2倍で12パターン存在する。これをすべて試して揃うものがあればYESを出力する。
回転する位置を配列で持っておき、配列から回転と判定をするようにすると実装量が落ちて楽。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

int a[24], b[24];

bool check() {
  REP(i, 6) {
    bool flag = true;
    FOR(j, 1, 4) {
      if(a[i*4] != a[i*4+j]) {
        flag = false;
        break;
      }
    }
    if(!flag) return false;
  }
  return true;
}

signed main(void)
{
  REP(i, 24) cin >> a[i], b[i] = a[i];

  int tmp1, tmp2;
  VI v;

  // 1
  v = {1, 3, 5, 7, 9, 11, 22, 20};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  // 2
  v = {0, 2, 4, 6, 8, 10, 23, 21};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  // 3
  v = {12, 13, 4, 5, 16, 17, 20, 21};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  // 4
  v = {14, 15, 6, 7, 18, 19, 22, 23};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  // 5
  v = {2, 3, 16, 18, 9, 8, 15, 13};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];

  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;

  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  // 6
  v = {0, 1, 17, 19, 11, 10, 14, 12};
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];
  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;
  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];
  reverse(ALL(v));
  tmp1 = a[v[0]], tmp2 = a[v[1]];
  for(int i=0; i<6; i+=2) {
    a[v[i]] = a[v[i+2]];
    a[v[i+1]] = a[v[i+3]];
  }
  a[v[6]] = tmp1, a[v[7]] = tmp2;
  if(check()) {
    cout << "YES" << endl;
    return 0;
  }
  REP(i, 24) a[i] = b[i];

  cout << "NO" << endl;

  return 0;
}