結果

問題 No.43 野球の試合
ユーザー ngtkana
提出日時 2020-03-27 01:38:16
言語 C++17(1z)
(gcc 9.3.0)
結果
AC  
実行時間 18 ms
コード長 997 Byte
コンパイル時間 1,956 ms
使用メモリ 8,948 KB
最終ジャッジ日時 2020-03-27 01:38:20

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 2 ms
8,940 KB
sample2.txt AC 2 ms
8,944 KB
sample3.txt AC 2 ms
8,948 KB
sample4.txt AC 2 ms
6,900 KB
test1.txt AC 3 ms
8,944 KB
test2.txt AC 2 ms
8,940 KB
test3.txt AC 18 ms
6,900 KB
test4.txt AC 18 ms
8,940 KB
test5.txt AC 17 ms
8,940 KB
test6.txt AC 17 ms
8,900 KB
test7.txt AC 17 ms
8,944 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
using lint=long long;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n;std::cin>>n;
    std::vector<std::string>a(n);
    for(auto&&s:a)std::cin>>s;
    lint N=1l<<n*(n-1)/2;
    lint ans=n;
    for(lint bs=0;bs<N;bs++){
        std::vector<std::vector<lint>>b(n,std::vector<lint>(n));
        for(lint i=0,k=0;i<n;i++){
            for(lint j=i+1;j<n;j++,k++){
                char c=a.at(i).at(j);
                b.at(i).at(j)=c=='-'?bs>>i&1:c=='o';
                b.at(j).at(i)=!b.at(i).at(j);
            }
        }
        lint win=0;
        std::vector<lint>ckd(n+1);
        for(lint i=0;i<n;i++){
            lint x=std::accumulate(b.at(i).begin(),b.at(i).end(),0ll);
            if(i==0)win=x;
            ckd.at(x)=true;
        }
        lint now=std::count(ckd.begin()+win,ckd.end(),true);
        if(now<ans)ans=now;
    }
    std::cout<<ans<<'\n';
}
0