結果

問題 No.1937 Various Tournament
ユーザー noya2noya2
提出日時 2021-12-26 18:03:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 849 ms / 2,000 ms
コード長 2,762 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 213,620 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 02:42:58
合計ジャッジ時間 29,425 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 799 ms
5,376 KB
testcase_02 AC 824 ms
5,376 KB
testcase_03 AC 819 ms
5,376 KB
testcase_04 AC 809 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 815 ms
5,376 KB
testcase_07 AC 818 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 813 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 825 ms
5,376 KB
testcase_12 AC 813 ms
5,376 KB
testcase_13 AC 815 ms
5,376 KB
testcase_14 AC 819 ms
5,376 KB
testcase_15 AC 809 ms
5,376 KB
testcase_16 AC 828 ms
5,376 KB
testcase_17 AC 820 ms
5,376 KB
testcase_18 AC 849 ms
5,376 KB
testcase_19 AC 815 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 813 ms
5,376 KB
testcase_23 AC 807 ms
5,376 KB
testcase_24 AC 821 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 826 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 811 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 828 ms
5,376 KB
testcase_31 AC 814 ms
5,376 KB
testcase_32 AC 830 ms
5,376 KB
testcase_33 AC 804 ms
5,376 KB
testcase_34 AC 824 ms
5,376 KB
testcase_35 AC 820 ms
5,376 KB
testcase_36 AC 826 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 813 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 819 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 822 ms
5,376 KB
testcase_46 AC 3 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
testcase_49 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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