oj.uz

Submission #547885

# Submission time Handle Problem Language Result Execution time Memory
547885 2022-04-12T01:08:43 Z Olympia Boat (APIO16_boat) C++17
0 / 100
 261 ms 4348 KB 
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

const int M = 1e9 + 7;
const int MOD = 1e9 + 7;
using namespace std;
int64_t binPow (int64_t x, int64_t y) {
    int64_t ans = 1, res = x;
    while (y) {
        if (y & 1) ans *= res, ans %= MOD;
        res *= res, res %= MOD, y /= 2;
    }
    return ans;
}
int64_t inv (int64_t x) {
    return binPow(x, MOD - 2);
}
struct modint {
    modint() : n(0) {}
    template <class T> modint(T n) { n %= M; if (n < 0) n += M; this->n = n; }

    modint & operator+=(const modint &r) { n += r.n; if (n >= M) n -= M; return *this; }
    modint & operator-=(const modint &r) { n -= r.n; if (n < 0) n += M; return *this; }
    modint & operator*=(const modint &r) { n = (int) ((long long) n * r.n % M); return *this; }

    modint & operator--() { if (--n == -1) n = M - 1; return *this; }
    modint & operator++() { if (++n == M) n = 0; return *this; }
    modint operator--(int) { modint t = *this; --*this; return t; }
    modint operator++(int) { modint t = *this; ++*this; return t; }

    modint operator-() const { return 0 - *this; }
    modint operator+() const { return *this; }

    modint pow(long long k = M - 2) const {
        modint f = *this, p = 1;
        while (k > 0) {
            if (k % 2 == 1) f *= p;
            p *= p, k /= 2;
        }
        return f;
    }

    int mod() const { return M; }

    friend modint operator+(modint l, const modint &r) { return l += r; }
    friend modint operator-(modint l, const modint &r) { return l -= r; }
    friend modint operator*(modint l, const modint &r) { return l *= r; }

    friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }
    friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }

    friend ostream & operator<<(ostream &out, const modint &r) { return out << r.n; }

    int n;
};

vector<pair<int,int>> compress (vector<pair<int,int>> &vec) {
    set<int> s;
    for (auto& p: vec) {
        s.insert(p.first), s.insert(p.second);
    }
    vector<int> v; for (int i: s) v.push_back(i);
    vector<pair<int,int>> grids;
    grids.emplace_back(-1, -1);
    for (int i = 0; i < v.size(); i++) {
        grids.emplace_back(v[i], v[i]);
        if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
    }
    return grids;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N; cin >> N;
    vector<pair<int,int>> points(N);
    for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
    vector<pair<int,int>> grid = compress(points);
    modint combo[grid.size()][N + 1];
    for (int i = 0; i < grid.size(); i++) {
        combo[i][0] = 1;
        for (int j = 1; j <= N; j++) {
            combo[i][j] = (combo[i][j - 1] * ((modint)j).pow()) * (grid[i].second - grid[i].first - j + 2);
        }
        for (int j = grid[i].second - grid[i].first + 2; j <= N; j++) {
            combo[i][j] = 0;
        }
    }
    modint dp[N + 1][grid.size()];
    for (int i = 0; i <= N; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i < grid.size(); i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < grid.size(); j++) {
            dp[i][j] = dp[i][j - 1];
            int pos = 0;
            for (int k = i; k >= 1; k--) {
                if (grid[j].first >= points[k - 1].first && grid[j].second <= points[k - 1].second) {
                    pos ++;
                    dp[i][j] += (dp[k - 1][j - 1]) * combo[j][pos];
                }
            }
        }
    }
    cout << dp[N][grid.size() - 1] - 1;
}

Compilation message

boat.cpp: In function 'std::vector<std::pair<int, int> > compress(std::vector<std::pair<int, int> >&)':
boat.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
boat.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
      |             ~~~~~~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
boat.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
boat.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int j = 1; j < grid.size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 4264 KB Output is correct
2 Correct 247 ms 4268 KB Output is correct
3 Correct 261 ms 4172 KB Output is correct
4 Correct 242 ms 4256 KB Output is correct
5 Correct 245 ms 4264 KB Output is correct
6 Correct 159 ms 4348 KB Output is correct
7 Correct 150 ms 4260 KB Output is correct
8 Correct 155 ms 4236 KB Output is correct
9 Correct 158 ms 4264 KB Output is correct
10 Correct 158 ms 4300 KB Output is correct
11 Correct 154 ms 4264 KB Output is correct
12 Correct 157 ms 4264 KB Output is correct
13 Correct 151 ms 4172 KB Output is correct
14 Correct 146 ms 4256 KB Output is correct
15 Correct 153 ms 4264 KB Output is correct
16 Incorrect 51 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 4264 KB Output is correct
2 Correct 247 ms 4268 KB Output is correct
3 Correct 261 ms 4172 KB Output is correct
4 Correct 242 ms 4256 KB Output is correct
5 Correct 245 ms 4264 KB Output is correct
6 Correct 159 ms 4348 KB Output is correct
7 Correct 150 ms 4260 KB Output is correct
8 Correct 155 ms 4236 KB Output is correct
9 Correct 158 ms 4264 KB Output is correct
10 Correct 158 ms 4300 KB Output is correct
11 Correct 154 ms 4264 KB Output is correct
12 Correct 157 ms 4264 KB Output is correct
13 Correct 151 ms 4172 KB Output is correct
14 Correct 146 ms 4256 KB Output is correct
15 Correct 153 ms 4264 KB Output is correct
16 Incorrect 51 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 4264 KB Output is correct
2 Correct 247 ms 4268 KB Output is correct
3 Correct 261 ms 4172 KB Output is correct
4 Correct 242 ms 4256 KB Output is correct
5 Correct 245 ms 4264 KB Output is correct
6 Correct 159 ms 4348 KB Output is correct
7 Correct 150 ms 4260 KB Output is correct
8 Correct 155 ms 4236 KB Output is correct
9 Correct 158 ms 4264 KB Output is correct
10 Correct 158 ms 4300 KB Output is correct
11 Correct 154 ms 4264 KB Output is correct
12 Correct 157 ms 4264 KB Output is correct
13 Correct 151 ms 4172 KB Output is correct
14 Correct 146 ms 4256 KB Output is correct
15 Correct 153 ms 4264 KB Output is correct
16 Incorrect 51 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -