Submission #154424

# Submission time Handle Problem Language Result Execution time Memory
154424 2019-09-21T18:54:35 Z srvlt Energetic turtle (IZhO11_turtle) C++14
5 / 100
2000 ms 600 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 = 700000;
int n, m, k, t, z, ans, phi;
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 >>= 1LL;
    }
    return res;
}

int c(int a, int b) {
    if (a < 0) {
        return 0;
    }
    int res = 1;
	for (int i = 1; i <= a; i++) {
		res = res * (b - a + i) / i;
		res %= z;
	}
	return res;
}

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);
    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 < (1LL << k); i++) {
        int sgn = 1;
        if (__builtin_popcountll(i) > t) {
            sgn = -1;
        }
        pii last = {0, 0};
        int res = 1;
        bool wrong = false;
        for (int j = 0; j < k; j++) {
            if (i & (1LL << j)) {
                int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1;
                if (v[j].fi < last.fi || v[j].se < last.se) {
                    wrong = true;
                    break;
                }
                int tmp = c(dx - 2, dx + dy - 3) + c(dx - 1, dx + dy - 3);
                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();
    }
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Incorrect 6 ms 376 KB Output isn't correct
3 Incorrect 6 ms 376 KB Output isn't correct
4 Incorrect 53 ms 600 KB Output isn't correct
5 Execution timed out 2005 ms 376 KB Time limit exceeded
6 Incorrect 82 ms 376 KB Output isn't correct
7 Incorrect 751 ms 504 KB Output isn't correct
8 Incorrect 37 ms 376 KB Output isn't correct
9 Execution timed out 2055 ms 376 KB Time limit exceeded
10 Execution timed out 2065 ms 376 KB Time limit exceeded
11 Execution timed out 2083 ms 376 KB Time limit exceeded
12 Execution timed out 2005 ms 504 KB Time limit exceeded
13 Incorrect 1595 ms 476 KB Output isn't correct
14 Execution timed out 2011 ms 376 KB Time limit exceeded
15 Execution timed out 2069 ms 504 KB Time limit exceeded
16 Execution timed out 2025 ms 424 KB Time limit exceeded
17 Execution timed out 2062 ms 376 KB Time limit exceeded
18 Execution timed out 2012 ms 476 KB Time limit exceeded
19 Execution timed out 2080 ms 248 KB Time limit exceeded
20 Execution timed out 2074 ms 376 KB Time limit exceeded