oj.uz

Submission #986072

# Submission time Handle Problem Language Result Execution time Memory
986072 2024-05-19T17:35:25 Z salmon Boat (APIO16_boat) C++14
0 / 100
 199 ms 524 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
pair<int,int> lst[510];
int a, b;
long long int mod = 1'000'000'007;
long long int p[510];
long long int fact[510];
vector<int> de;
vector<int> bat[1100];
map<int,int> mep;

long long int expo(long long int x, long long int b, long long int mul){
    if(mul == 0) return x;
    if(mul % 2 == 1){
        return expo(x * b % mod, b * b % mod, mul / 2);
    }
    else{
        return expo(x, b * b % mod, mul / 2);
    }
}

int main(){

    scanf(" %d",&N);

    for(int i = 1; i <= N; i++){
        scanf(" %d",&a);
        scanf(" %d",&b);

        lst[i] = {a,b};

        de.push_back(a);
        de.push_back(b + 1);
        p[i] = 0;
    }

    p[N + 1] = 0;
    p[0] = 1;

    fact[0] = 1;
    for(int i = 1; i < 510; i++){
        fact[i] = fact[i - 1] *  i % mod;
    }

    sort(de.begin(),de.end());
    de.resize(unique(de.begin(),de.end()) - de.begin());

    for(int i = 0; i < de.size(); i++){
        mep[de[i]] = i;
    }

    for(int i = 1; i <= N; i++){
        for(int j = 0; j < de.size(); j++){
            if(lst[i].first <= de[j] && de[j] <= lst[i].second){
                bat[j].push_back(i);
            }
        }
    }
    bat[de.size() - 1].push_back(N + 1);
    de.push_back(1100100100);

    for(int i = 0; i < de.size() - 1; i++){
        long long int mul[510];

        int c = de[i + 1] - de[i];

        mul[0] = c;

        for(int i = 1; i < 509; i++){
            mul[i] = mul[i - 1] * (i + c) % mod;
        }

        for(int i = 0; i < 509; i++){
            mul[i] = expo(mul[i], fact[i + 1], mod - 2);
            //printf("%lld ",mul[i]);
        }

        vector<int> v = {0};
        long long int pst[510];

        for(int i = 0; i <= 501; i++){
            pst[i] = 0;
        }

        for(int j = 0; j < bat[i].size(); j++){
            v.push_back(bat[i][j]);
            long long int sum = 0;

            for(int k = 0; k < v.size() - 1; k++){
                int ni = v.size();


                for(int i = v[ni - 2 - k]; i <= v[ni - 1 - k] - 1; i++){
                    sum = (sum + p[i] * mul[k]) % mod;
                }
            }

            pst[bat[i][j]] = sum;
        }

        for(int i = 0; i <= 501; i++){
            p[i] = (p[i] + pst[i]) % mod;
        }
    }

    long long int ans = 0;

    for(int i = 1; i <= N; i++){
        ans += p[i];
    }


    printf("%lld",ans);
}
/*
3
1 2
2 4
2 4

2
1 2
2 4

3
2 2
4 4
4 4
*/

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < de.size(); i++){
      |                    ~~^~~~~~~~~~~
boat.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j = 0; j < de.size(); j++){
      |                        ~~^~~~~~~~~~~
boat.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < de.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~
boat.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j = 0; j < bat[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
boat.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int k = 0; k < v.size() - 1; k++){
      |                            ~~^~~~~~~~~~~~~~
boat.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
boat.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
boat.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf(" %d",&b);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -