AtCoder Regular Contest 062

Submission #1364608

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}
 
using i64=int64_t;

void shift(vector<int> &a){
    rotate(a.begin(),a.begin()+1,a.end());
};

void normalize(vector<int>& a){
    auto amin=a;
    rep(i,0,4){
        amin=min(amin,a);
        shift(a);
    }
    a=amin;
}

i64 encode(vector<int>& a){
    i64 res=0;
    rep(i,0,4){
        res*=1000;
        res+=a[i];
    }
    return res;
}

vector<int> reverse(vector<int> &a){
    auto b=a;
    swap(b[0],b[1]);
    swap(b[3],b[2]);
    return b;
}

int f(vector<int>& a){
    if(a[0]==a[1] and a[1]==a[2] and a[2]==a[3]) return 4;
    if(a[0]==a[2] and a[1]==a[3]) return 2;
    return 1;
}

void input(int& N,vector<vector<int>> &C){
    cin >> N;
    C.resize(N);
    rep(i,0,N){
        C[i].resize(4);
        cin >> C[i][0] >> C[i][1] >> C[i][2] >> C[i][3];
        normalize(C[i]);
    }
}

void solve(){
    int N;
    vector<vector<int>> C;
    input(N,C);

    map<i64,i64> count[5]; //1,2,4
    rep(i,0,N) ++count[f(C[i])][encode(C[i])];
 
    auto make_sides=[&](int i,int j){
        vector<vector<int>> sides(4,vector<int>(4));
        rep(k,0,4){
            sides[k][0]=C[i][(k+1)%4];
            sides[k][1]=C[i][k];
            sides[k][2]=C[j][k];
            sides[k][3]=C[j][(k+1)%4];
        }
        return sides;
    };
 
    i64 ans=0;
    rep(i,0,N){
        --count[f(C[i])][encode(C[i])];
        rep(j,i+1,N){
            --count[f(C[j])][encode(C[j])];
            C[j]=reverse(C[j]);
            rep(k,0,4){
                auto sides=make_sides(i,j);
                for(auto &side:sides) normalize(side);
                i64 tmp=count[f(sides[0])][encode(sides[0])]*f(sides[0]);
                tmp*=(count[f(sides[1])][encode(sides[1])]-(encode(sides[0])==encode(sides[1])))*f(sides[1]);
                tmp*=(count[f(sides[2])][encode(sides[2])]-((encode(sides[0])==encode(sides[2]))+(encode(sides[1])==encode(sides[2]))))*f(sides[2]);
                tmp*=(count[f(sides[3])][encode(sides[3])]-((encode(sides[0])==encode(sides[3]))+(encode(sides[1])==encode(sides[3]))+(encode(sides[2])==encode(sides[3]))))*f(sides[3]);
                ans+=tmp;
                shift(C[j]);
            }
            C[j]=reverse(C[j]);
            ++count[f(C[j])][encode(C[j])];
        }
    }
    
    cout << ans << endl;
}
 
int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission

Task問題 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
User nameユーザ名 walkre
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 900
Source lengthソースコード長 3066 Byte
File nameファイル名
Exec time実行時間 985 ms
Memory usageメモリ使用量 80128 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 258 ms 256 KB
1_004.txt AC 20 ms 256 KB
1_005.txt AC 269 ms 256 KB
1_006.txt AC 189 ms 256 KB
1_007.txt AC 273 ms 256 KB
1_008.txt AC 245 ms 256 KB
1_009.txt AC 292 ms 256 KB
1_010.txt AC 44 ms 256 KB
1_011.txt AC 343 ms 384 KB
1_012.txt AC 3 ms 384 KB
1_013.txt AC 985 ms 68352 KB
1_014.txt AC 7 ms 1024 KB
1_015.txt AC 893 ms 80000 KB
1_016.txt AC 189 ms 22272 KB
1_017.txt AC 890 ms 80128 KB
1_018.txt AC 896 ms 80000 KB
1_019.txt AC 912 ms 78976 KB