oj.uz

Submission #154403

# Submission time Handle Problem Language Result Execution time Memory
154403 2019-09-21T17:31:38 Z srvlt Energetic turtle (IZhO11_turtle) C++14
5 / 100
 1109 ms 29304 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, lp[M + 3], f[M + 3], fr[M + 3];
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;
}

int c(int a, int b) {
    return (f[b] * fr[a] % z) * fr[b - a] % z;
}

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;
    lp[1] = 1;
    for (int i = 2; i <= M; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= M; j += i) {
                prime[j] = false;
                if (!lp[j]) {
                    lp[j] = i;
                }
            }
            lp[i] = i;
        }
    }
    int phi = getphi(z);
    f[0] = fr[0] = 1;
    for (int i = 1; i <= M; i++) {
        f[i] = f[i - 1] * i % z;
        fr[i] = fr[i - 1] * binpow(i, phi - 1) % z;
    }

    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;
        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;
                int tmp = c(dx - 1, dx + dy - 2);
                res = res * tmp % z;
                last = v[j];
            }
        }
        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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 14456 KB Output is correct
2 Incorrect 477 ms 14516 KB Output isn't correct
3 Incorrect 236 ms 14464 KB Output isn't correct
4 Incorrect 384 ms 14628 KB Output isn't correct
5 Incorrect 895 ms 14720 KB Output isn't correct
6 Incorrect 296 ms 14504 KB Output isn't correct
7 Incorrect 314 ms 14436 KB Output isn't correct
8 Incorrect 296 ms 14624 KB Output isn't correct
9 Incorrect 444 ms 14712 KB Output isn't correct
10 Runtime error 317 ms 29196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 322 ms 29240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 323 ms 29256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 480 ms 29228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 555 ms 14640 KB Output isn't correct
15 Runtime error 492 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 490 ms 29272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 488 ms 29280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Incorrect 1109 ms 14556 KB Output isn't correct
19 Incorrect 1104 ms 14588 KB Output isn't correct
20 Runtime error 492 ms 29220 KB Execution killed with signal 11 (could be triggered by violating memory limits)