oj.uz

Submission #844836

# Submission time Handle Problem Language Result Execution time Memory
844836 2023-09-06T03:41:50 Z AndriaBeridze Energetic turtle (IZhO11_turtle) C++14
50 / 100
 1272 ms 44380 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 % z;
        f1[i] = f1[i - 1] * pow(i, z - 2, z) % z;
    }

    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
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 44124 KB Output is correct
2 Incorrect 132 ms 44380 KB Output isn't correct
3 Correct 51 ms 44260 KB Output is correct
4 Correct 81 ms 44124 KB Output is correct
5 Correct 466 ms 44256 KB Output is correct
6 Correct 71 ms 44124 KB Output is correct
7 Correct 93 ms 44260 KB Output is correct
8 Correct 70 ms 44260 KB Output is correct
9 Correct 169 ms 44256 KB Output is correct
10 Correct 273 ms 44260 KB Output is correct
11 Correct 96 ms 44260 KB Output is correct
12 Incorrect 273 ms 44372 KB Output isn't correct
13 Incorrect 131 ms 44264 KB Output isn't correct
14 Incorrect 275 ms 44260 KB Output isn't correct
15 Incorrect 540 ms 44252 KB Output isn't correct
16 Incorrect 537 ms 44120 KB Output isn't correct
17 Incorrect 229 ms 44120 KB Output isn't correct
18 Incorrect 1272 ms 44260 KB Output isn't correct
19 Incorrect 1271 ms 44264 KB Output isn't correct
20 Incorrect 540 ms 44252 KB Output isn't correct