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
Task E - Building Cubes with AtCoDeer
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 900
Code Size 3142 Byte
Status
Exec Time 394 ms
Memory 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