Codeforces 464B Restore Cube 暴力枚舉全排列判斷正方體（另一實現）

與 265D 異同

Codeforces 464B 與 265D 為同一題不同輪次，邏輯完全一致。本文提供另一風格實現：結構體運算符重載、next_permutation 直接作用於數組、DFS 固定首行。

代碼亮點

struct Point {
    long long x[3];
    void input() { for (int i=0;i<3;++i) scanf("%lld",&x[i]); }
    void output() { printf("%lld %lld %lld\n",x[0],x[1],x[2]); }
    Point operator-(const Point& o) const {
        Point r; for(int i=0;i<3;++i) r.x[i]=x[i]-o.x[i]; return r;
    }
};
long long dist2(Point a) { return a.x[0]*a.x[0]+a.x[1]*a.x[1]+a.x[2]*a.x[2]; }

bool check(int k) {
    long long d[7]; int c=0;
    for(int i=0;i<8;++i) if(i!=k) d[c++]=dist2(p[k]-p[i]);
    sort(d,d+7);
    return d[0]>0 && d[0]==d[1] && d[0]==d[2] &&
           d[3]==d[4] && d[3]==d[5] && d[3]==2*d[0] &&
           d[6]==3*d[0];
}

bool dfs(int dep) {
    if(dep==8) { if(check_all()) { print_ans(); return true; } return false; }
    sort(p[dep].x, p[dep].x+3);
    do { if(dfs(dep+1)) return true; } while(next_permutation(p[dep].x, p[dep].x+3));
    return false;
}

優化細節

• 運算符重載簡化距離計算；
• check 合併所有判斷條件為單一返回表達式；
• 主程序固定 dfs(1)，首行不排列。

複雜度與通過率

6⁷ × 8 × 7 ≈ 1.1e8 基本操作，C++ O2 優化後 ~0.3s 通過 1s 時限。