Submission #273403


Source Code Expand

Copy
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cmath>
#include <complex>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
#include <valarray>
#include <list>

using namespace std;

typedef long long ll;

template<class T>
struct Pi {
    T x, y;
    Pi() {}
    Pi(T xx, T yy) {
        x = xx; y = yy;
    }
    bool operator<(const Pi &r) const {
        if (x != r.x) return x < r.x;
        return y < r.y;
    }
    bool operator>(const Pi &r) const {
        if (x != r.x) return x > r.x;
        return y > r.y;
    }
    bool operator==(const Pi &r) const {
        if (x != r.x) return false;
        return y == r.y;
    }
};

template<class T>
struct Ti {
    T x, y, z;
    Ti() {}
    Ti(T xx, T yy, T zz) {
        x = xx; y = yy; z = zz;
    }
    bool operator<(const Ti &r) const {
        if (x != r.x) return x < r.x;
        if (y != r.y) return y < r.y;
        return z < r.z;
    }
    bool operator>(const Ti &r) const {
        if (x != r.x) return x > r.x;
        if (y != r.y) return y > r.y;
        return z > r.z;
    }
    bool operator==(const Ti &r) const {
        if (x != r.x) return false;
        if (y != r.y) return false;
        return z == r.z;
    }
};

struct SMatrix {
    typedef double D;
    vector<valarray<D>> d;
    int N, M;
    SMatrix(int n, int m) {
        N = n; M = m;
        d.resize(n);
        for (int i = 0; i < N; i++) {
            d[i] = valarray<D>(D(0), m);
        }
    }

    valarray<D>& operator[](int p) {
        return d[p];
    }
    
    const valarray<D>& operator[](int p) const {
        return d[p];
    }
    
    SMatrix& operator=(const SMatrix &other) {
        assert(other.N == N && other.M == M);
        copy_n(other.d.begin(), N, d.begin());
        return *this;
    }

    SMatrix operator+(const SMatrix &right) {
        assert(right.N == N && right.M == M);
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = d[i]+right[i];
        }
        return res;
    }
    
    SMatrix operator*(const SMatrix &right) {
        assert(M == right.N);
        SMatrix res(N, right.M), r(right.M, right.N);
        for (int i = 0; i < right.M; i++) {
            for (int j = 0; j < right.N; j++) {
                r[i][j] = right[j][i]; 
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < right.M; j++) {
                res[i][j] = (d[i]*r[j]).sum();
            }
        }
        return res;
    }

    SMatrix operator*(const D x) {
        SMatrix res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = d[i]*x;
        }
        return res;
    }

    SMatrix pow(ll p) {
        assert(N == M);
        SMatrix res(N, M), buf = *this;
        for (int i = 0; i < N; i++) res[i][i] = D(1);
        while(p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }
};

int main() {
    double p;
    ll n;
    cin >> p >> n;
    SMatrix m = SMatrix(2, 2);
    m[0][0] = 1-p;
    m[0][1] = p;
    m[1][0] = p;
    m[1][1] = 1-p;
    m = m.pow(n);
    printf("%.20f\n", m[0][1]);
    return 0;
}

Submission Info

Submission Time
Task A - eject
User yosupo
Language C++11 (GCC 4.8.1)
Score 0
Code Size 3505 Byte
Status WA
Exec Time 25 ms
Memory 928 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 23
WA × 10
Set Name Test Cases
All 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 10-random_small-09, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 20-random_large-05, 20-random_large-06, 20-random_large-07, 20-random_large-08, 20-random_large-09, 30-p_zero-00, 30-p_zero-01, 30-p_zero-02, 30-p_zero-03, 30-p_zero-04, 40-p_one-00, 40-p_one-01, 40-p_one-02, 40-p_one-03, 40-p_one-04, 90-handmade-00
Case Name Status Exec Time Memory
00-sample-00 AC 22 ms 804 KB
00-sample-01 AC 20 ms 920 KB
10-random_small-00 AC 25 ms 928 KB
10-random_small-01 AC 21 ms 928 KB
10-random_small-02 AC 23 ms 800 KB
10-random_small-03 AC 23 ms 804 KB
10-random_small-04 AC 23 ms 736 KB
10-random_small-05 AC 21 ms 672 KB
10-random_small-06 AC 23 ms 728 KB
10-random_small-07 AC 23 ms 800 KB
10-random_small-08 AC 22 ms 800 KB
10-random_small-09 AC 21 ms 796 KB
20-random_large-00 WA 21 ms 800 KB
20-random_large-01 WA 23 ms 800 KB
20-random_large-02 WA 22 ms 800 KB
20-random_large-03 WA 24 ms 804 KB
20-random_large-04 WA 22 ms 796 KB
20-random_large-05 WA 22 ms 676 KB
20-random_large-06 WA 23 ms 748 KB
20-random_large-07 WA 24 ms 700 KB
20-random_large-08 WA 23 ms 804 KB
20-random_large-09 WA 22 ms 924 KB
30-p_zero-00 AC 24 ms 800 KB
30-p_zero-01 AC 23 ms 800 KB
30-p_zero-02 AC 23 ms 808 KB
30-p_zero-03 AC 23 ms 920 KB
30-p_zero-04 AC 21 ms 928 KB
40-p_one-00 AC 20 ms 924 KB
40-p_one-01 AC 23 ms 732 KB
40-p_one-02 AC 24 ms 796 KB
40-p_one-03 AC 21 ms 804 KB
40-p_one-04 AC 21 ms 796 KB
90-handmade-00 AC 23 ms 736 KB