AtCoder Regular Contest 062

Submission #1357262

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;

int N;

vector<vector<int>> input(){
    cin >> N;
    vector<vector<int>> C(N,vector<int>(4));
    rep(i,0,N) cin >> C[i][0] >> C[i][1] >> C[i][2] >> C[i][3];
    random_shuffle(C.begin(),C.end());
    return C;
}
 
void solve(){
    auto C=input();
    vector<vector<vector<int>>> rotatedC(N,vector<vector<int>>(4,vector<int>(4)));
    vector<i64> Csum(N),Cpro(N);
    rep(i,0,N){
        Cpro[i]=1;
        rep(j,0,4){
            Csum[i]+=C[i][j];
            Cpro[i]*=C[i][j];
        }
        rep(j,0,4){
            rotatedC[i][j]=C[i];
            rotate(C[i].begin(),C[i].begin()+1,C[i].end());
        }
    }
 
    auto match=[](vector<int>& a,vector<int>& b){
        rep(i,0,4) if(a[i]!=b[i]) return false;
        return true;
    };
 
    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;
    };
 
    auto reverse=[&](vector<int> &a){
        auto b=a;
        swap(b[0],b[1]);
        swap(b[3],b[2]);
        return b;
    };

    auto shift=[&](vector<int> &a){
        auto b=a;
        rotate(b.begin(),b.begin()+1,b.end());
        return b;
    };

    auto normalize=[&](vector<vector<int>> &a){
        rep(i,0,4){
            auto amin=a[i];
            rep(j,0,4){
                amin=min(amin,a[i]);
                a[i]=shift(a[i]);
            }
        }
        sort(a.begin(),a.begin());
    };
 
    i64 ans=0;
    rep(i,0,N){
        rep(j,i+1,N){
            vector<vector<int>> sides;
            static i64 memo[401][1<<4];
            fill_n((i64*)memo,(N+1)*16,-1);
            vector<pair<int,int>> update;
            vector<int> indexes;
            vector<i64> sum(4),pro(4);
            function<i64(int,int)> rec=[&](int k,int b){
                auto &res=memo[k][b];
                if(res!=-1) return res;
                update.push_back(make_pair(k,b));
                if(b==((1<<4)-1)) return res=1;
                if(k==indexes.size()) return res=0;
                res=rec(k+1,b);
                rep(i_,0,4){
                    if(b&(1<<i_) or Csum[indexes[k]]!=sum[i_] or Cpro[indexes[k]]!=pro[i_]) continue;
                    rep(j_,0,4) if(match(rotatedC[indexes[k]][j_],sides[i_])) res+=rec(k+1,b|(1<<i_));
                }
                return res;
            };
 
            C[j]=reverse(C[j]);
            rep(k,0,4){
                auto next_sides=make_sides(i,j);
                normalize(next_sides);
                if(next_sides!=sides){
                    for(auto& u:update) memo[u.first][u.second]=-1;
                    update.clear();
                    indexes.clear();
                    sides=next_sides;
                    rep(i_,0,4){
                        sum[i_]=0;
                        pro[i_]=1;
                        rep(j_,0,4){
                            sum[i_]+=sides[i_][j_];
                            pro[i_]*=sides[i_][j_];
                        }
                    }
                }

                rep(i_,i+1,N){
                    if(i_==j) continue;
                    bool use=false;
                    rep(j_,0,4) if(Csum[i_]==sum[j_] and Cpro[i_]==pro[j_]){
                        use=true;
                        break;
                    }
                    if(use) indexes.push_back(i_);
                }
                
                ans+=rec(0,0);

                C[j]=shift(C[j]);
            }
            C[j]=reverse(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状態 TLE
Score得点 0
Source lengthソースコード長 4534 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt
All 0 / 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 2 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt TLE
1_004.txt AC 664 ms 384 KB
1_005.txt TLE
1_006.txt TLE
1_007.txt TLE
1_008.txt TLE
1_009.txt TLE
1_010.txt AC 274 ms 384 KB
1_011.txt AC 1416 ms 512 KB
1_012.txt AC 4 ms 256 KB
1_013.txt AC 982 ms 384 KB
1_014.txt AC 7 ms 256 KB
1_015.txt AC 932 ms 384 KB
1_016.txt AC 198 ms 384 KB
1_017.txt AC 951 ms 384 KB
1_018.txt AC 945 ms 384 KB
1_019.txt AC 953 ms 384 KB