oj.uz

답안 #557319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557319 2022-05-05T06:47:10 Z kwongweng Boat (APIO16_boat) C++17
9 / 100
 248 ms 1620 KB 
/*
Solution for APIO 2016 - Boat
Tags : 
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
vector<ll> inv(501,-1);
ll inverse(ll n){
    if (inv[n] != -1) return inv[n];
	return inv[n] = power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}
 
vector<ll> cnt[1000];
// cnt[i][j] = # solution for first ith school with last student sent is in ith compartment from left, and there are j students in the compartment
 
void solve(){
    int n; cin >> n;
    vector<ll> a(n), b(n); FOR(i,0,n) cin >> a[i] >> b[i];
    vector<pair<ll,int>> pos;
    FOR(i,0,n){
        b[i]++;
        pos.pb({a[i], i});
        pos.pb({b[i], i});
    }
    sort(pos.begin(), pos.end());
    vi l(n,-1), r(n,-1);
    FOR(i,0,2*n){
        int j = pos[i].se;
        if (l[j] == -1) l[j] = i;
        else r[j] = i;
    }
    FOR(i,0,2*n-1){
        cnt[i].pb(0);
    }
    FOR(i,0,n){
        ll total = 1;
        FOR(j,0,l[i]){
            for (ll val2 : cnt[j]){
                total += val2;
                total %= MOD;
            }
        }
        //compartment from l[i] to r[i]
        vector<ll> val(i+2);
        FOR(j,0,r[i]-l[i]){
            val[0] = 0;
            ll interval = pos[j+l[i]+1].fi - pos[j+l[i]].fi;
            val[1] = mul(interval,total);
            for (ll val2 : cnt[j+l[i]]){
                total += val2;
                total %= MOD;
            }
            FOR(k,2,i+2){
                ll new_val = 0;
                if (cnt[j+l[i]].size()>=k) new_val = cnt[j+l[i]][k-1];
                if (new_val == 0){
                    break;
                }
                ll binom = mul(interval - k + 1, inverse(k)) ; // 
                new_val = mul(new_val, binom);
                val[k] = new_val;
            }
            FOR(k,1,i+2){
                if (k>=cnt[j+l[i]].size()){
                    if (val[k] == 0) break;
                    cnt[j+l[i]].pb(val[k]);
                    continue;
                } 
                cnt[j+l[i]][k] = (cnt[j+l[i]][k] + val[k]) % MOD;
            }
        }
    }
    ll ans = 0;
    FOR(i,0,2*n-1){
        for (ll val2 : cnt[i]){
            ans = add(ans, val2);
        }
    }
    cout << ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

boat.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
boat.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
boat.cpp: In function 'void solve()':
boat.cpp:99:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |                 if (cnt[j+l[i]].size()>=k) new_val = cnt[j+l[i]][k-1];
      |                     ~~~~~~~~~~~~~~~~~~^~~
boat.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if (k>=cnt[j+l[i]].size()){
      |                     ~^~~~~~~~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:129:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:130:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Incorrect 248 ms 1620 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Incorrect 248 ms 1620 KB Output isn't correct
22 Halted 0 ms 0 KB -