Submission #2205682
Source Code Expand
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <functional> using namespace std; #define Rep(b, e, i) for(int i = b; i <= e; i++) #define rep(n, i) Rep(0, n-1, i) const int MAX = 200000; const double PI = 3.14159265358979323846; const double EPS = 1e-12; const int INF = 1<<31-1; const int MOD = 1000000007; typedef long long ll; typedef pair<ll, ll> llP; typedef pair<int, int> intP; typedef std::priority_queue<int> IntPrioQueue; //Z->A typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z ll fac[MAX+1],facInv[MAX+1]; ll power(ll e, ll x){ //e^x % MOD if (x == 0) return 1LL; if (x % 2 != 0) return ((power(e, x-1) * e) % MOD); ll temp = power(e, x / 2); return (temp * temp) % MOD; } ll nck(ll n, ll k){ if (!(n >= k && k >= 0)) return 0; ll temp = (fac[n] * facInv[n-k]) % MOD; return ((temp * facInv[k]) % MOD); } void fact(void){ //階乗とその逆元 fac[0] = facInv[0] = 1; //0! = 1 //(x!)^(-1) ≡ (x!)^(p-2) (mod p) Rep(1, MAX, i) fac[i] = (fac[i-1] * i) % MOD; facInv[MAX] = power(fac[MAX], MOD-2); Rep(1, MAX-1, i) facInv[MAX-i] = (facInv[MAX-i+1] * (MAX-i+1)) % MOD; } void solve(void){ int N; cin >> N; int coins[N]; rep(N, i) scanf("%d\n", &coins[i]); vector <int> w(N); rep(N, i) w[i] = i; double tails = 0; do { rep(N, i) { int c = 0; rep(i, j) if (coins[w[i]]%coins[w[j]]==0) c++; if (c%2==0) tails++; } } while(next_permutation(w.begin(), w.end())); fact(); printf("%.6lf\n", tails/fac[N]); } int main(void){ solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - コイン |
User | sifi_border |
Language | C++14 (GCC 5.4.1) |
Score | 99 |
Code Size | 1932 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 3328 KB |
Compile Error
./Main.cpp: In function ‘void solve()’: ./Main.cpp:60:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] rep(N, i) scanf("%d\n", &coins[i]); ^
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 99 / 99 | 0 / 1 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt |
Subtask2 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 4 ms | 3328 KB |
sample_02.txt | AC | 4 ms | 3328 KB |
sample_03.txt | AC | 4 ms | 3328 KB |
subtask1_01.txt | AC | 5 ms | 3328 KB |
subtask1_02.txt | AC | 5 ms | 3328 KB |
subtask1_03.txt | AC | 5 ms | 3328 KB |
subtask1_04.txt | AC | 9 ms | 3328 KB |
subtask1_05.txt | AC | 10 ms | 3328 KB |
subtask1_06.txt | AC | 5 ms | 3328 KB |
subtask1_07.txt | AC | 9 ms | 3328 KB |
subtask1_08.txt | AC | 4 ms | 3328 KB |
subtask1_09.txt | AC | 4 ms | 3328 KB |
subtask1_10.txt | AC | 9 ms | 3328 KB |
subtask1_11.txt | AC | 4 ms | 3328 KB |
subtask1_12.txt | AC | 9 ms | 3328 KB |
subtask1_13.txt | AC | 5 ms | 3328 KB |
subtask1_14.txt | AC | 5 ms | 3328 KB |
subtask1_15.txt | AC | 9 ms | 3328 KB |
subtask1_16.txt | AC | 9 ms | 3328 KB |
subtask1_17.txt | AC | 9 ms | 3328 KB |
subtask1_18.txt | AC | 9 ms | 3328 KB |
subtask1_19.txt | AC | 9 ms | 3328 KB |
subtask1_20.txt | AC | 9 ms | 3328 KB |
subtask2_01.txt | AC | 574 ms | 3328 KB |
subtask2_02.txt | TLE | 2103 ms | 256 KB |
subtask2_03.txt | TLE | 2103 ms | 256 KB |
subtask2_04.txt | TLE | 2103 ms | 256 KB |
subtask2_05.txt | TLE | 2103 ms | 256 KB |
subtask2_06.txt | TLE | 2103 ms | 256 KB |
subtask2_07.txt | TLE | 2103 ms | 256 KB |
subtask2_08.txt | TLE | 2103 ms | 256 KB |
subtask2_09.txt | TLE | 2103 ms | 256 KB |
subtask2_10.txt | TLE | 2103 ms | 256 KB |
subtask2_11.txt | TLE | 2103 ms | 256 KB |
subtask2_12.txt | TLE | 2103 ms | 256 KB |
subtask2_13.txt | TLE | 2103 ms | 256 KB |
subtask2_14.txt | TLE | 2103 ms | 256 KB |
subtask2_15.txt | TLE | 2103 ms | 256 KB |
subtask2_16.txt | TLE | 2103 ms | 256 KB |
subtask2_17.txt | TLE | 2103 ms | 256 KB |
subtask2_18.txt | TLE | 2103 ms | 256 KB |
subtask2_19.txt | TLE | 2103 ms | 256 KB |
subtask2_20.txt | TLE | 2103 ms | 256 KB |