結果
問題 | No.43 野球の試合 |
ユーザー | troro_kelp |
提出日時 | 2019-01-06 01:34:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 2,535 bytes |
コンパイル時間 | 1,881 ms |
コンパイル使用メモリ | 107,200 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 23:40:23 |
合計ジャッジ時間 | 1,652 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 9 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
ソースコード
#include <stdio.h> #include <iostream> #include <string> #include <vector> #include <set> #include <cmath> #include <stack> #include <algorithm> #include <iomanip> #include <map> #include <queue> #include <functional> #include <numeric> #include <chrono> #include <cstdlib> using ll = long long; using namespace std; const ll MOD = 1e9 + 7; #define REP(i, n) for (int(i) = 0; (i) < (n); ++(i)) #define repi(i, a, b) for (int i = int(a); i < int(b); ++i) // bool operator<(const pair<int, int> &a, const pair<int, int> &b) // { // if (a.first == b.first) // return a.second < b.second; // return a.first < b.first; // }; /*unsigned int xor128(void) { static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned int xor128rnd(unsigned int m) { return xor128() % m; }*/ /*bool operator<(const pair<int, int> &a, const pair<int, int> &b) { if (a.first == b.first) { return a.second < b.second; } return a.first < b.first; }*/ int ans = 1000000; int N; vector<string> v; void dfs(int a, int b) { // for (int i = 0; i < N; ++i) // { // for (int j = 0; j < N; ++j) // { // cout << v[i][j]; // } // cout << endl; // } // cout << endl; if (a == N) { vector<int> vec(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (v[i][j] == 'o') vec[i]++; } } //cout << endl; int t = vec[0]; sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (int i = 0; i < (int)vec.size(); ++i) { if (vec[i] == t) { ans = min(ans, (int)vec.size() - i); break; } } return; } if (b == N) { dfs(a + 1, 0); return; } if (v[a][b] != '-') { dfs(a, b + 1); return; } v[a][b] = 'o'; v[b][a] = 'x'; dfs(a, b + 1); v[a][b] = 'x'; v[b][a] = 'o'; dfs(a, b + 1); v[a][b] = v[b][a] = '-'; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int i = 0; i < N; ++i) { string s; cin >> s; v.push_back(s); } dfs(0, 0); cout << ans << endl; return 0; }