Submission #5629771
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef vector<pll> vpll;
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
inline void IN(void){
return;
}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
cin >> first;
IN(rest...);
return;
}
inline void OUT(void){
cout << "\n";
return;
}
template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
cout << first << " ";
OUT(rest...);
return;
}
template <typename T>
void vec_print(vector<T> VEC){
REP(i, VEC.size()){
cout << VEC[i] << " ";
}
cout << "\n";
};
template <typename T>
void mat_print(vector<vector<T> > MAT){
REP(i, MAT.size()){
REP(j, MAT[i].size()){
cout << MAT[i][j] << " ";
}
cout << "\n";
}
};
template <typename CLASS1, typename CLASS2>
class HOGE{
public:
CLASS1 key;
CLASS2 value;
HOGE(void){
return;
};
HOGE(CLASS1 key, CLASS2 value){
this->key = key;
this->value = value;
};
~HOGE(void){
return;
};
void print(void){
cout << "key : " << key << ", value : " << value << "\n";
return;
};
bool operator==(const HOGE &obj){
return (this->value == obj.value);
};
bool operator<(const HOGE &obj){
return (this->value < obj.value);
};
bool operator>(const HOGE &obj){
return (this->value > obj.value);
};
};
template <typename CLASS1, typename CLASS2>
bool operator==(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value == hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator<(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value < hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator>(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value > hoge2.value;
};
constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);
vll R;
vector<vector<double> > Ratio; // i win when i vs j
int main(){
cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)
ll K;
IN(K);
ll n=(1LL<<K);
R.resize(n);
REP(i,n) IN(R[i]);
Ratio.resize(n, vector<double>(n));
REP(i,n) REP(j,n){
Ratio[i][j] = 1.0/(1.0 + pow(10.0, (R[j]-R[i])/400.0));
}
vector<double> dp(n, 1.0);
ll dist = 1;
REP(k,K){
//1,...,dist vs dist+1,...,2*dist, 2*dist+1,...,3*dist vs 3*dist+1,...,4*dist, ...
//
vector<double> dp_copy = dp;
dp.assign(n, 0.0);
for(ll e=0; e<n; e+=2*dist){
REP(p,dist) REP(q,dist){
// e+p vs e+q+dist
dp[e+p] += dp_copy[e+p]*dp_copy[e+q+dist]*Ratio[e+p][e+q+dist];
dp[e+q+dist] += dp_copy[e+p]*dp_copy[e+q+dist]*Ratio[e+q+dist][e+p];
}
}
dist <<= 1;
}
REP(i,n){
printf("%.12lf\n", dp[i]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - トーナメント |
User |
fockl |
Language |
C++14 (GCC 5.4.1) |
Score |
4 |
Code Size |
3845 Byte |
Status |
AC |
Exec Time |
84 ms |
Memory |
8832 KB |
Judge Result
Set Name |
All |
Score / Max Score |
4 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
84 ms |
8832 KB |
01 |
AC |
80 ms |
8576 KB |
02 |
AC |
22 ms |
8576 KB |
03 |
AC |
80 ms |
8576 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |