oj.uz

Submission #154419

# Submission time Handle Problem Language Result Execution time Memory
154419 2019-09-21T18:33:18 Z srvlt Energetic turtle (IZhO11_turtle) C++14
10 / 100
 2000 ms 9976 KB 
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
const int M = 600000;
int n, m, k, t, z, ans, phi = 1;
vector <pii> v;
vector <bool> prime(M + 3, true);

int binpow(int x, int y) {
    int res = 1;
    while (y > 0) {
        if (y & 1) {
            res = res * x % z;
        }
        x = x * x % z;
        y >>= 1;
    }
    return res;
}

struct num {
    int a, b;
    num(int a = 0, int b = 0) {
        this -> a = a;
        this -> b = b;
    }
    void upd(num & x) {
        if (x.a % z == 0 && x.a > 0) {
            x.a /= z;
            x.b++;
        }   else {
            x.a %= z;
        }
    }
    void operator = (int x) {
        a = x;
        b = 0;
        if (a % z == 0 && a > 0) {
            a /= z;
            b++;
        }   else {
            a %= z;
        }
    }
    void operator = (const num & x) {
        a = x.a;
        b = x.b;
    }
    num operator * (const num & x) {
        num res;
        res.b = b + x.b;
        res.a = a * x.a;
        upd(res);
        return res;
    }
    num operator / (const num & x) {
        num res;
        res.b = b - x.b;
        int tmp = binpow(x.a, phi - 1);
        res.a = a * tmp;
        upd(res);
        return res;
    }
    num operator + (int x) {
        num res;
        res.b = b;
        if (res.b > 0) {
            res.a = x;
            res.b = 0;
        }   else {
            res.a = a + x;
        }
        upd(res);
        return res;
    }
};

num f[M + 3];

int c(int a, int b) {
    num res = f[b] / f[a] / f[b - a];
    if (res.b > 0) {
        return 0;
    }
    return res.a;
}

int getphi(int x) {
    if (x == 1) {
        return 1;
    }
    for (int i = 2; i * i <= x; i++) {
        if (prime[i] && x % i == 0) {
            int tmp = 1;
            while (x > 1 && x % i == 0) {
                tmp *= i;
                x /= i;
            }
            tmp /= i;
            return getphi(x) * tmp * (i - 1) % z;
        }
    }
    return (x - 1) % z;
}

void solve(int tc) {
    cin >> n >> m >> k >> t >> z;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= M; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= M; j += i) {
                prime[j] = false;
            }
        }
    }
    phi = getphi(z);
    f[0] = num(1, 0);
    for (int i = 1; i <= M; i++) {
        f[i] = f[i - 1] * num(i, 0);
    }

    for (int i = 0; i < k; i++) {
        pii p;
        cin >> p.fi >> p.se;
        v.pb(p);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < (1 << k); i++) {
        int sgn = 1;
        if (__builtin_popcount(i) > t) {
            sgn = -1;
        }
        pii last = {0, 0};
        int res = 1;
        bool wrong = false;
        for (int j = 0; j < k; j++) {
            if (i & (1 << j)) {
                int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1;
                if (dy < 1) {
                    wrong = true;
                    break;
                }
                int tmp = c(dx - 1, dx + dy - 2);
                res = res * tmp % z;
                last = v[j];
            }
        }
        if (wrong) {
            continue;
        }
        int dx = n - last.fi + 1, dy = m - last.se + 1;
        int tmp = c(dx - 1, dx + dy - 2);
        res = res * tmp % z;
        ans = (ans + res * sgn + z) % z;
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9848 KB Output is correct
2 Incorrect 26 ms 9848 KB Output isn't correct
3 Incorrect 26 ms 9848 KB Output isn't correct
4 Incorrect 84 ms 9844 KB Output isn't correct
5 Incorrect 1414 ms 9860 KB Output isn't correct
6 Incorrect 37 ms 9848 KB Output isn't correct
7 Incorrect 121 ms 9856 KB Output isn't correct
8 Incorrect 27 ms 9848 KB Output isn't correct
9 Incorrect 444 ms 9976 KB Output isn't correct
10 Incorrect 806 ms 9860 KB Output isn't correct
11 Incorrect 151 ms 9860 KB Output isn't correct
12 Correct 704 ms 9852 KB Output is correct
13 Incorrect 30 ms 9860 KB Output isn't correct
14 Incorrect 1773 ms 9856 KB Output isn't correct
15 Execution timed out 2060 ms 9976 KB Time limit exceeded
16 Execution timed out 2016 ms 9848 KB Time limit exceeded
17 Incorrect 611 ms 9856 KB Output isn't correct
18 Execution timed out 2039 ms 9820 KB Time limit exceeded
19 Execution timed out 2037 ms 9848 KB Time limit exceeded
20 Execution timed out 2008 ms 9848 KB Time limit exceeded