oj.uz

답안 #63231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63231 2018-08-01T06:36:21 Z qkxwsm Boat (APIO16_boat) C++17
9 / 100
 2000 ms 9116 KB 
/*
PROG: source
LANG: C++11
    _____
  .'     '.
 /  0   0  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
        int operator()(int x) const
        {
                x ^= (x >> 20) ^ (x >> 12);
                return x ^ (x >> 7) ^ (x >> 4);
        }
        int operator()(long long x) const
        {
                return x ^ (x >> 32);
        }
};

template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
        {
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
template<class T, class U>
T normalize(T x, U mod = 1000000007)
{
	return (((x % mod) + mod) % mod);
}
long long randomizell(long long mod)
{
	return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
int randomize(int mod)
{
	return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 513

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N;
pii arr[MAXN];
vector<int> compress;
ll dp[MAXN][2 * MAXN], pref[MAXN][2 * MAXN];
ll modinv[MAXN], ifact[MAXN];
ll nchoose[MAXN][MAXN], pchoose[MAXN];
ll prec[MAXN];
ll ans;

ll getpow(ll a, ll e)
{
        if (e == 1)
        {
                return a;
        }
        ll was = getpow(a, e / 2);
        if (e & 1)
        {
                return was * was % INF * a % INF;
        }
        return was * was % INF;
}
int getidx(int v)
{
        return UB(compress.begin(), compress.end(), v) - compress.begin() - 1;
}
ll choose(ll n, ll k)
{
        if (k < 0 || k > n) return 0;
        ll res = ifact[k];
        for (int i = 0; i < k; i++)
        {
                res *= (n - i);
                res %= INF;
        }
        return res;
}
void precchoose(ll k)
{
        ll prod = 1;
        pchoose[0] = 1;
        for (int i = 1; i <= N; i++)
        {
                prod *= (k - i + 1);
                prod %= INF;
                pchoose[i] = prod * ifact[i] % INF;
                // cerr << k << " choose " << i << " = " << pchoose[i] << endl;
        }
        return;
}
ll f(ll m, ll k)
{
        //put m guys into k slots
        ll res = 0;
        for (int i = 0; i <= m; i++)
        {
                // res += nchoose[m][i] * pchoose[i];
                res += nchoose[m][i] * pchoose[i];
                res %= INF;
        }
        // cerr << "fit " << m << " into " << k << ' ' << res << endl;
        return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	srand(time(0));
	//	cout << fixed << setprecision(10);
	//	cerr << fixed << setprecision(10);
	if (fopen("input.in", "r"))
	{
		freopen ("input.in", "r", stdin);
		freopen ("output.out", "w", stdout);
	}
        cin >> N;
        ifact[0] = 1; ifact[1] = 1; modinv[1] = 1;
        for (int i = 2; i <= N; i++)
        {
                modinv[i] = getpow(i, INF - 2);
                ifact[i] = ifact[i - 1] * modinv[i];
                ifact[i] %= INF;
        }
        for (int i = 0; i <= N; i++)
        {
                nchoose[i][0] = 1;
                nchoose[i][i] = 1;
                for (int j = 1; j < i; j++)
                {
                        nchoose[i][j] = nchoose[i - 1][j - 1] + nchoose[i - 1][j];
                        nchoose[i][j] %= INF;
                }
        }
        for (int i = 0; i < N; i++)
        {
                cin >> arr[i].fi >> arr[i].se;
                arr[i].se++;
                compress.PB(arr[i].fi);
                compress.PB(arr[i].se);
                // cerr << arr[i].fi << ',' << arr[i].se << endl;
        }
        compress.PB(0);
        sort(compress.begin(), compress.end());
        compress.erase(unique(compress.begin(), compress.end()), compress.end());
        // cerr << "positions:";
        // for (int x : compress)
        // {
        //         cerr << ' ' << x;
        // }
        // cerr << endl;
        dp[0][0] = 1;
        pref[0][0] = 1;
        for (int k = 1; k < compress.size() - 1; k++)
        {
                ll spots = compress[k + 1] - compress[k];
                precchoose(spots);
                for (int i = 0; i <= N; i++)
                {
                        prec[i] = f(i, spots);
                }
                for (int i = 1; i <= N; i++)
                {
                        if (compress[k] < arr[i - 1].fi || compress[k] >= arr[i - 1].se)
                        {
                                continue;
                        }
                        int oks = 0;
                        for (int j = i - 1; j >= 0; j--)
                        {
                                if (arr[j].fi <= compress[k] && compress[k] < arr[j].se)
                                {
                                        oks++;
                                }
                                //you finish at j, but at any position less than k
                                //j...i - 1 are all in, and i - 1 MUST be active!
                                ll net = pref[j][k - 1];
                                // cerr << "person " << j - 1 << " finishes less than " << k << ' ' << net << endl;
                                ll fits = f(oks, spots) - f(oks - 1, spots);
                                // ll fits = (prec[oks] - prec[oks - 1] + INF) % INF;
                                dp[i][k] += net * fits;
                                dp[i][k] %= INF;
                                // cerr << "inside " << compress[k] << " oks " << oks << endl;
                                // cerr << "oks " << oks << " spots " << spots << endl;
                                // cerr << "good ways to fit " << j << " to " << i - 1 << " in " << k << " is " << fits << endl;
                        }
                        // cerr << "guy " << i - 1 << " finish " << k << ' ' << dp[i][k] << endl;
                        // pref[i][k] = pref[i][k - 1] + dp[i][k]; //person i finishes at positoin k
                        // pref[i][k] %= INF;
                }
                for (int i = 0; i <= N; i++)
                {
                        pref[i][k] = pref[i][k - 1] + dp[i][k];
                        pref[i][k] %= INF;
                }
        }
        for (int i = 1; i <= N; i++)
        {
                for (int j = 1; j < compress.size() - 1; j++)
                {
                        ans += dp[i][j];
                        ans %= INF;
                }
        }
        cout << ans << '\n';
	//	cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}

Compilation message

boat.cpp: In function 'int32_t main()':
boat.cpp:255:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k = 1; k < compress.size() - 1; k++)
                         ~~^~~~~~~~~~~~~~~~~~~~~
boat.cpp:300:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 1; j < compress.size() - 1; j++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~
boat.cpp:215:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("input.in", "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:216:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("output.out", "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 731 ms 8552 KB Output is correct
2 Correct 768 ms 8552 KB Output is correct
3 Correct 742 ms 8608 KB Output is correct
4 Correct 750 ms 8660 KB Output is correct
5 Correct 744 ms 8704 KB Output is correct
6 Correct 733 ms 9016 KB Output is correct
7 Correct 747 ms 9016 KB Output is correct
8 Correct 796 ms 9016 KB Output is correct
9 Correct 756 ms 9016 KB Output is correct
10 Correct 732 ms 9016 KB Output is correct
11 Correct 736 ms 9048 KB Output is correct
12 Correct 739 ms 9048 KB Output is correct
13 Correct 766 ms 9048 KB Output is correct
14 Correct 775 ms 9048 KB Output is correct
15 Correct 770 ms 9116 KB Output is correct
16 Correct 144 ms 9116 KB Output is correct
17 Correct 152 ms 9116 KB Output is correct
18 Correct 151 ms 9116 KB Output is correct
19 Correct 170 ms 9116 KB Output is correct
20 Correct 161 ms 9116 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 731 ms 8552 KB Output is correct
2 Correct 768 ms 8552 KB Output is correct
3 Correct 742 ms 8608 KB Output is correct
4 Correct 750 ms 8660 KB Output is correct
5 Correct 744 ms 8704 KB Output is correct
6 Correct 733 ms 9016 KB Output is correct
7 Correct 747 ms 9016 KB Output is correct
8 Correct 796 ms 9016 KB Output is correct
9 Correct 756 ms 9016 KB Output is correct
10 Correct 732 ms 9016 KB Output is correct
11 Correct 736 ms 9048 KB Output is correct
12 Correct 739 ms 9048 KB Output is correct
13 Correct 766 ms 9048 KB Output is correct
14 Correct 775 ms 9048 KB Output is correct
15 Correct 770 ms 9116 KB Output is correct
16 Correct 144 ms 9116 KB Output is correct
17 Correct 152 ms 9116 KB Output is correct
18 Correct 151 ms 9116 KB Output is correct
19 Correct 170 ms 9116 KB Output is correct
20 Correct 161 ms 9116 KB Output is correct
21 Execution timed out 2043 ms 9116 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 9116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 731 ms 8552 KB Output is correct
2 Correct 768 ms 8552 KB Output is correct
3 Correct 742 ms 8608 KB Output is correct
4 Correct 750 ms 8660 KB Output is correct
5 Correct 744 ms 8704 KB Output is correct
6 Correct 733 ms 9016 KB Output is correct
7 Correct 747 ms 9016 KB Output is correct
8 Correct 796 ms 9016 KB Output is correct
9 Correct 756 ms 9016 KB Output is correct
10 Correct 732 ms 9016 KB Output is correct
11 Correct 736 ms 9048 KB Output is correct
12 Correct 739 ms 9048 KB Output is correct
13 Correct 766 ms 9048 KB Output is correct
14 Correct 775 ms 9048 KB Output is correct
15 Correct 770 ms 9116 KB Output is correct
16 Correct 144 ms 9116 KB Output is correct
17 Correct 152 ms 9116 KB Output is correct
18 Correct 151 ms 9116 KB Output is correct
19 Correct 170 ms 9116 KB Output is correct
20 Correct 161 ms 9116 KB Output is correct
21 Execution timed out 2043 ms 9116 KB Time limit exceeded
22 Halted 0 ms 0 KB -