Submission #931874


Source Code Expand

Copy
/*************************************************************************
  >         File: C.cc
  >       Author: lyyllyyl
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sat 15 Oct 2016 08:29:45 PM CST
*************************************************************************/
#include <bits/stdc++.h>
using LL = long long;
constexpr int N = 444;
std::vector<int> color[N];
std::map<std::vector<int>, int> has;
int corner[8];
int use[4][4] = {
  {0, 3, 6, 5},
  {0, 5, 4, 1},
  {1, 4, 7, 2},
  {2, 7, 6, 3}
};

void Add(std::vector<int> color) {
  for (int i = 0; i < 4; ++i) {
    has[color]++;
    std::rotate(color.begin(), color.begin() + 1, color.end());
  }
}

void Hide(std::vector<int> color) {
  for (int i = 0; i < 4; ++i) {
    has[color]--;
    std::rotate(color.begin(), color.begin() + 1, color.end());
  }
}

void Dfs(int dep, LL& ans, LL res = 1) {
  if (dep == 4) ans += res;
  else {
    std::vector<int> tmp(4);
    for (int i = 0; i < 4; ++i) tmp[i] = corner[use[dep][i]];
    if (has.count(tmp)) {
      int cnt = has[tmp];
      Hide(tmp);
      Dfs(dep + 1, ans, res * cnt);
      Add(tmp);
    }
  }
}

LL solve(int a, int b) {
  for (int i = 0; i < 4; ++i) {
    corner[i] = color[a][i];
    corner[i + 4] = color[b][i];
  }
  LL ans = 0;
  for (int i = 0; i < 4; ++i) {
    Dfs(0, ans);
    std::rotate(corner + 4, corner + 5, corner + 8);
  }
  return ans;
}

int main() {
  std::ios::sync_with_stdio(0);
#ifdef HOME
  std::string file(__FILE__);
  freopen((file.substr(0, file.find('.')) + ".in").c_str(), "r", stdin);
#endif
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    color[i].resize(4);
    for (int j = 0; j < 4; ++j) {
      std::cin >> color[i][j];
    }
    Add(color[i]);
  }
  LL answer = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      Hide(color[i]), Hide(color[j]);
      answer += solve(i, j);
      Add(color[i]), Add(color[j]);
      //std::cerr << "# i << ' ' << j << ' ' << answer # is " << i << ' ' << j << ' ' << answer << std::endl;
    }
    Hide(color[i]);
  }
  std::cout << answer << std::endl;
  std::cerr << "---------------------------" << std::endl;
  std::cerr << "Time used: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec." << std::endl;
  return 0;
}

Submission Info

Submission Time
Task E - Building Cubes with AtCoDeer
User Yoshioka
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2363 Byte
Status
Exec Time 1234 ms
Memory 512 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_000.txt, 0_001.txt, 0_002.txt
All 900 / 900 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt
Case Name Status Exec Time Memory
0_000.txt 3 ms 256 KB
0_001.txt 3 ms 256 KB
0_002.txt 3 ms 256 KB
1_003.txt 450 ms 256 KB
1_004.txt 35 ms 256 KB
1_005.txt 697 ms 256 KB
1_006.txt 494 ms 256 KB
1_007.txt 991 ms 256 KB
1_008.txt 877 ms 256 KB
1_009.txt 1234 ms 384 KB
1_010.txt 100 ms 256 KB
1_011.txt 266 ms 384 KB
1_012.txt 3 ms 256 KB
1_013.txt 161 ms 512 KB
1_014.txt 4 ms 256 KB
1_015.txt 156 ms 512 KB
1_016.txt 42 ms 384 KB
1_017.txt 157 ms 512 KB
1_018.txt 157 ms 512 KB
1_019.txt 161 ms 512 KB