結果

問題 No.1937 Various Tournament
ユーザー noya2noya2
提出日時 2021-12-26 18:03:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 994 ms / 2,000 ms
コード長 2,762 bytes
コンパイル時間 2,695 ms
コンパイル使用メモリ 206,848 KB
最終ジャッジ日時 2025-01-27 07:14:18
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::vector<long long int> solve(std::vector<int>)’:
main.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define repp(i,n,m) for (int i = m; i < int(n); ++i)
using namespace std;
using ll = long long;

int n;
vector<vector<int>> win(16,vector<int>(16,0));

vector<ll> solve(vector<int> join){
    int m = join.size();
    if (m == 16){
        vector<ll> ans(16,0);
        rep(a,9) repp(b,10,a+1) repp(c,11,b+1) repp(d,12,c+1) repp(e,13,d+1) repp(f,14,e+1) repp(g,15,f+1){
            vector<int> x = {a,b,c,d,e,f,g,15};
            vector<int> _cnt(16,0);
            rep(i,8) _cnt[x[i]]++;
            vector<int> y;
            rep(i,16) if (_cnt[i] == 0) y.emplace_back(i);
            vector<ll> p = solve(x);
            vector<ll> q = solve(y);
            rep(i,8) rep(j,8){
                if (win[x[i]][y[j]] == 1) ans[x[i]] += p[i] * q[j] * 2;
                else ans[y[j]] += p[i] * q[j] * 2;
            }
        }
        return ans;
    }
    if (m == 8){
        vector<ll> ans(8,0);
        rep(a,5) repp(b,6,a+1) repp(c,7,b+1){
            vector<int> inda = {a,b,c,7};
            vector<int> indb;
            vector<int> _cnt(8,0);
            rep(i,4) _cnt[inda[i]]++;
            rep(i,8) if (_cnt[i] == 0) indb.emplace_back(i);
            vector<int> x(4), y(4);
            rep(i,4) x[i] = join[inda[i]];
            rep(i,4) y[i] = join[indb[i]];
            vector<ll> p = solve(x);
            vector<ll> q = solve(y);
            rep(i,4) rep(j,4){
                if (win[x[i]][y[j]] == 1) ans[inda[i]] += p[i] * q[j] * 2;
                else ans[indb[j]] += p[i] * q[j] * 2;
            }
        }
        return ans;
    }
    if (m == 4){
        vector<ll> ans(4,0);
        rep(a,3){
            vector<int> inda = {a,3};
            vector<int> indb;
            vector<int> _cnt(4,0);
            rep(i,2) _cnt[inda[i]]++;
            rep(i,4) if (_cnt[i] == 0) indb.emplace_back(i);
            vector<int> x(2), y(2);
            rep(i,2) x[i] = join[inda[i]];
            rep(i,2) y[i] = join[indb[i]];
            vector<ll> p(2,0);
            vector<ll> q(2,0);
            if (win[x[0]][x[1]] == 1) p[0] = 2;
            else p[1] = 2;
            if (win[y[0]][y[1]] == 1) q[0] = 2;
            else q[1] = 2;
            rep(i,2) rep(j,2){
                if (win[x[i]][y[j]] == 1) ans[inda[i]] += p[i] * q[j] * 2;
                else ans[indb[j]] += p[i] * q[j] * 2;
            }
        }
        return ans;
    }
    if (m == 2){
        vector<ll> ans(2,0);
        if (win[0][1] == 1) ans[0] = 2;
        else ans[1] = 2;
        return ans;
    }
}

int main(){
    cin >> n;
    rep(i,n) rep(j,n) cin >> win[i][j];
    vector<int> c(n);
    rep(i,n) c[i] = i;
    vector<ll> ans = solve(c);
    rep(i,n) cout << ans[i] << endl;
}
0