FACUP - The FA cup

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, N;
int a[1025][1025];
pair<double, int> ds[1025];

vector<double> calc( int left, int right) {
	vector<double> res;
	if(left==right) {
		res.push_back(1);
		return res;
	}
	int mid = (left+right) / 2;
	vector<double> r1 = calc( left, mid);
	vector<double> r2 = calc( mid+1, right);
	for(int i=left;i<=mid;++i) {
		double t = 0;
		for(int j=mid+1;j<=right;++j)
			t += r2[j-mid-1] * a[i][j] / 100.0;
		res.push_back( t * r1[i-left] );
	}
	for(int i=mid+1;i<=right;++i) {
		double t = 0;
		for(int j=left;j<=mid;++j)
			t += r1[j-left] * a[i][j] / 100.0;
		res.push_back( t * r2[i-mid-1] );
	}
	return res;
}

bool cmp(pair< double, int > p1, pair<double, int> p2) {
	if(p1.first==p2.first) return p1.second < p2.second;
	return p1.first > p2.first;
}

int main() {
	scanf("%d", &n);
	N = 1<<n;
	for(int i=0;i<N;++i) for(int j=0;j<N;++j) scanf("%d", a[i]+j);
	vector<double> res = calc( 0, N-1);
	for(int i=0;i<N;++i) ds[i] = make_pair( res[i], i+1);
	sort( ds, ds + N, cmp);
	for(int i=0;i<N;++i) printf("%d\n", ds[i].second);
	//system("pause");
	return 0;
}

Download