Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #931294

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> T input(istream & in) { T a; in >> a; return a; }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }
typedef uint16_t color_t;
array<color_t,4> rotate(array<color_t,4> c, int r) {
rotate(c.begin(), c.begin() + r, c.end());
return c;
}
void normalize(array<color_t,4> & c) {
array<color_t,4> d = c;
repeat (r,4) setmin(c, rotate(d, r));
}
int multiplicity(array<color_t,4> const & c) {
int n = 0;
repeat (r,4) if (c == rotate(c, r)) n += 1;
return n;
}
int main() {
int n; cin >> n;
vector<array<color_t,4> > c(n);
repeat (i,n) repeat (j,4) cin >> c[i][j];
repeat (i,n) normalize(c[i]);
map<array<color_t,4>,int> cnt; repeat (i,n) cnt[c[i]] += 1;
map<array<color_t,4>,int> mul; for (auto it : cnt) mul[it.first] = multiplicity(it.first);
ll ans = 0;
repeat (bi,n) repeat (ai,bi) { // div 2
cnt[c[ai]] -= 1;
cnt[c[bi]] -= 1;
repeat (br,4) { // div 4
//    b0 -- b3
//   /     / |
// a0 -- a1  |
//  | _1  | b2
//  |     | /
// a3 -- a2
array<color_t,4> const & a = c[ai];
array<color_t,4> b = rotate(c[bi], br);
array<array<color_t,4>,4> ds;
ds[0] = { b[0], b[3], a[1], a[0] };
ds[1] = { b[3], b[2], a[2], a[1] };
ds[2] = { b[2], b[1], a[3], a[2] };
ds[3] = { b[1], b[0], a[0], a[3] };
ll acc = 1;
map<array<color_t,4>,int> used;
for (auto & d : ds) {
normalize(d);
if (not cnt.count(d)) { acc = 0; break; }
used[d] += 1;
acc *= mul[d] * (cnt[d] - used[d] + 1);
}
ans += acc;
}
cnt[c[ai]] += 1;
cnt[c[bi]] += 1;
}
assert (ans % 3 == 0);
ans /= 3;
cout << ans << endl;
return 0;
}
```

#### Submission Info

Submission Time 2016-10-15 22:04:08+0900 E - Building Cubes with AtCoDeer kimiyuki C++14 (GCC 5.4.1) 900 3142 Byte AC 394 ms 256 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 177 ms 256 KB
1_004.txt 15 ms 256 KB
1_005.txt 254 ms 256 KB
1_006.txt 178 ms 256 KB
1_007.txt 344 ms 256 KB
1_008.txt 308 ms 256 KB
1_009.txt 394 ms 256 KB
1_010.txt 35 ms 256 KB
1_011.txt 90 ms 256 KB
1_012.txt 3 ms 256 KB
1_013.txt 63 ms 256 KB
1_014.txt 3 ms 256 KB
1_015.txt 62 ms 256 KB
1_016.txt 18 ms 256 KB
1_017.txt 63 ms 256 KB
1_018.txt 62 ms 256 KB
1_019.txt 64 ms 256 KB