結果

問題 No.43 野球の試合
ユーザー naimonon77naimonon77
提出日時 2016-05-20 16:36:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,642 bytes
コンパイル時間 1,915 ms
コンパイル使用メモリ 175,340 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 01:05:43
合計ジャッジ時間 2,305 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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 5 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define SQR(X)  ( (X)*(X) )
#define CUBE(X) ( (X)*(X)*(X) )
#define ALL(a) (a).begin(),(a).end()
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;
 
 
void reader(int &a){scanf("%d",&a);}
void reader(double &a){scanf("%lf",&a);}
void reader(char a[]){scanf("%s",a);}
void reader(ll &a){scanf("%lld",&a);}
void reader(ull &a){scanf("%llu",&a);}
// void reader(string& a){cin >> a;};
template<class T,class U> void reader(T& t,U& u){reader(t); reader(u);}
template<class T,class U,class V> void reader(T& t,U& u,V& v){reader(t); reader(u); reader(v);}
 
void writer(int a,char c) {printf("%d",a); putchar(c);}
void writer(ll a,char c) {printf("%lld",a); putchar(c);}
void writer(double a,char c) {printf("%.20lf",a); putchar(c);}
void writer(char a[]) {printf("%s",a);};
void writer(char a[],char c) {printf("%s",a);putchar(c);};
void writer(char a,char c) {putchar(a); putchar(c);};
template<class T>void writerLn(T t){writer(t,'\n');}
template<class T,class U>void writerLn(T t,U u){writer(t,' ');writer(u,'\n');}
template<class T,class U,class V> void writerLn(T t,U u,V v){writer(t,' ');writer(u,' ');writer(v,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){putchar('\n');return;}rep(i,n-1) writer(x[i],' ');writer(x[n-1],'\n');}
template<class T> void writerVec(vector<T> x){int n=x.size();int i;if(!n){putchar('\n');return;}rep(i,n-1) writer(x[i],' ');writer(x[n-1],'\n');}
 

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
// #define int ll
 
int n;
bool test = 1;
vector< pair<int,int> > route;
void dfs(int& ans,char s[][7],int a
		 ,vector<int>& win) {
  if(a != route.size()) {
	int i = route[a].first;
	int j = route[a].second;
	if(s[i][j] == '-') {
	  s[i][j] = '!';
	  win[i]++;
	  dfs(ans,s,a+1,win);
	  win[i]--;
	  win[j]++;
	  dfs(ans,s,a+1,win);
	  win[j]--;
	  s[i][j] = '-';
	  return;
	}
  }
  int rank = 1;
  vector<int> tmp = win;
  sort(ALL(tmp),greater<int>());
  rep(i,n) {
	if(i) {
	  if(tmp[i] != tmp[i-1]) rank++;
	}
	if(tmp[i] == win[0]) break;
  }
  if(rank < ans) ans = rank;
}
//............................
#define MAX 300000
signed main(){
  int i,j,k,l;
  cin >> n;
  char s[6][7];
  rep(i,n) cin >> s[i];
  vector<int> win(6);
  int ans = 100;
  rep(i,n) {
	REP(j,i+1,n) {
	  if(s[i][j] == 'o') win[i] += 1;
	  if(s[i][j] == 'x') win[j] += 1;
	  if(s[i][j] == '-') {
		route.push_back(make_pair(i,j));
	  }
	}
  }
  dfs(ans,s,0,win);
  cout << ans << endl;
  return 0;
}
0