oj.uz

Submission #844838

# Submission time Handle Problem Language Result Execution time Memory
844838 2023-09-06T03:44:32 Z AndriaBeridze Energetic turtle (IZhO11_turtle) C++14
5 / 100
 1217 ms 44372 KB 
#include<bits/stdc++.h>

using namespace std;
int TC = 0;

void dbg_out() {cout << endl;}
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {cout << " " << H; dbg_out(T...);}
#define debug(...) {cout << "(" << #__VA_ARGS__ << "):"; dbg_out(__VA_ARGS__);}

#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define add push_back
#define size(v) (int) v.size()
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define check() cout << "Why doesn't this stupid a** code work?" << endl;
#define inf (int) 1e18

vector<int> dp(5000005, -1);
vector<int> x, y;
int n, m, k, t, z;

vector<int> f(300005, 0), f1(300005, 0);

long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int C(int n, int k, int m){
    return f[n] * f1[n - k] % m * f1[k] % m;
}


int find(int i){
    if(dp[i] != -1){
        return dp[i];
    }
    int X = 0, Y = 0;
    for(int j = 0; j < 22; j++){
        if(i & (1 << j)){
            if(X > x[j]) dp[i] = 0;
            if(Y > y[j]) dp[i] = 0;
            X = x[j];
            Y = y[j];
        }
    }
    if(dp[i] != 0){
        if(__builtin_popcount(i) == 2){
            int l = -1, r = -1;
            for(int j = 0; j < 22; j++){
                if(i & (1 << j)){
                    if(l == -1) l = j;
                    r = j;
                }
            }
            dp[i] = C(abs(x[l] - x[r]) + abs(y[l] - y[r]), abs(x[l] - x[r]), z);
            int a = 0;
            for(int j = l; j <= r; j++){
                a += (1 << j);
            }
            for(int k = a; k; k = (k - 1) & a){
                if(!(k & (1 << l)) || !(k & (1 << r)) || i == k) continue;
                dp[i] -= find(k);
                dp[i] = (dp[i] + z) % z;
            }
        }
        else{
            vector<int> ind;
            for(int j = 0; j < 22; j++){
                if(i & (1 << j)) ind.push_back(j);
            }
            int a = 0, b = 0;
            for(int j = 0; j <= 1; j++) a += (1 << ind[j]);
            for(int j = 1; j < size(ind); j++) b += (1 << ind[j]);
            dp[i] = find(a) * find(b) % z;
        }
    }
    return dp[i];
}

void solve(){
    cin >> n >> m >> k >> t >> z;

    f[0] = f1[0] = 1;
    for(int i = 1; i <= 300000; i++){
        f[i] = f[i - 1] * i % (1000000007);
        f1[i] = f1[i - 1] * pow(i, 1000000005, 1000000007) % 1000000007;
    }

    vector<pair<int, int>> v = vector<pair<int,int>>(k + 2, {0, 0});
    x = y = vector<int>(k + 2, 0);
    for(int i = 1; i <= k; i++){
        cin >> x[i] >> y[i];
        v[i].first = x[i] + y[i];
        v[i].second = i;
    }

    x[0] = y[0] = 0;
    v[0].first = 0; v[0].second = 0;
    x[k + 1] = n, y[k + 1] = m;
    v[k + 1].first = n + m; v[k + 1].second = k + 1;

    sort(all(v));
    vector<int> a, b;
    for(int i = 0; i <= k + 1; i++){
        a.push_back(x[v[i].second]);
        b.push_back(y[v[i].second]);
    }
    x = a, y = b;

    for(int i = 0; i < (1 << (k + 2)); i++){
        if(__builtin_popcount(i) < 2) continue;
        dp[i] = find(i);
    }
    int ans = 0;
    int a1 = 0;
    for(int i = 0; i <= k + 1; i++){
        a1 += (1 << i);
    }
    for(int e = a1; e; e = (e - 1) & a1){
        if(__builtin_popcount(e) > t + 2 || !(e & 1) || !(e & (1 << (k + 1)))) continue;
        ans = (ans + dp[e]) % z;
    }
    cout << ans << endl;
}

signed main(){
    int q = 1;
    //cin >> q;
    while(++TC <= q){
    	solve();
    }
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 44120 KB Output is correct
2 Incorrect 41 ms 44124 KB Output isn't correct
3 Incorrect 43 ms 44124 KB Output isn't correct
4 Incorrect 54 ms 44124 KB Output isn't correct
5 Incorrect 461 ms 44124 KB Output isn't correct
6 Incorrect 44 ms 44264 KB Output isn't correct
7 Incorrect 66 ms 44120 KB Output isn't correct
8 Incorrect 42 ms 44260 KB Output isn't correct
9 Incorrect 144 ms 44120 KB Output isn't correct
10 Incorrect 250 ms 44256 KB Output isn't correct
11 Incorrect 67 ms 44280 KB Output isn't correct
12 Incorrect 243 ms 44260 KB Output isn't correct
13 Incorrect 42 ms 44124 KB Output isn't correct
14 Incorrect 188 ms 44268 KB Output isn't correct
15 Incorrect 451 ms 44256 KB Output isn't correct
16 Incorrect 464 ms 44372 KB Output isn't correct
17 Incorrect 146 ms 44124 KB Output isn't correct
18 Incorrect 1178 ms 44372 KB Output isn't correct
19 Incorrect 1217 ms 44260 KB Output isn't correct
20 Incorrect 448 ms 44120 KB Output isn't correct