oj.uz

Submission #557273

# Submission time Handle Problem Language Result Execution time Memory
557273 2022-05-05T05:13:52 Z kwongweng Boat (APIO16_boat) C++17
36 / 100
 2000 ms 6248 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;
}
 
ll inverse(ll n){
	return 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);
}

ll cnt[1000][501];
// 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;
    }
    ms(cnt,0,sizeof(cnt));
    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]
        int num = r[i]-l[i]; // # compartments
        vector<ll> val[num]; // val[i][j] = 
        FOR(j,0,r[i]-l[i]){
            val[j].pb(0);
            ll interval = pos[j+l[i]+1].fi - pos[j+l[i]].fi;
            val[j].pb(mul(interval,total));
            for (ll val2 : cnt[j+l[i]]){
                total += val2;
                total %= MOD;
            }
            FOR(k,2,i+2){
                ll new_val = cnt[j+l[i]][k-1];
                ll binom = mul(interval - k + 1, inverse(k)) ; // 
                new_val = mul(new_val, binom);
                val[j].pb(new_val);
            }
            FOR(k,1,i+2){
                cnt[j+l[i]][k] = add(cnt[j+l[i]][k], val[j][k]);
            }
        }
    }
    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 'int main()':
boat.cpp:117:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:118:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 4276 KB Output is correct
2 Correct 691 ms 4272 KB Output is correct
3 Correct 683 ms 4272 KB Output is correct
4 Correct 684 ms 4272 KB Output is correct
5 Correct 688 ms 4276 KB Output is correct
6 Correct 673 ms 4280 KB Output is correct
7 Correct 673 ms 4280 KB Output is correct
8 Correct 665 ms 4276 KB Output is correct
9 Correct 660 ms 4180 KB Output is correct
10 Correct 641 ms 4280 KB Output is correct
11 Correct 643 ms 4300 KB Output is correct
12 Correct 637 ms 4272 KB Output is correct
13 Correct 636 ms 4180 KB Output is correct
14 Correct 645 ms 4276 KB Output is correct
15 Correct 655 ms 4272 KB Output is correct
16 Correct 946 ms 4340 KB Output is correct
17 Correct 960 ms 4532 KB Output is correct
18 Correct 974 ms 4436 KB Output is correct
19 Correct 968 ms 4416 KB Output is correct
20 Correct 968 ms 4440 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 4276 KB Output is correct
2 Correct 691 ms 4272 KB Output is correct
3 Correct 683 ms 4272 KB Output is correct
4 Correct 684 ms 4272 KB Output is correct
5 Correct 688 ms 4276 KB Output is correct
6 Correct 673 ms 4280 KB Output is correct
7 Correct 673 ms 4280 KB Output is correct
8 Correct 665 ms 4276 KB Output is correct
9 Correct 660 ms 4180 KB Output is correct
10 Correct 641 ms 4280 KB Output is correct
11 Correct 643 ms 4300 KB Output is correct
12 Correct 637 ms 4272 KB Output is correct
13 Correct 636 ms 4180 KB Output is correct
14 Correct 645 ms 4276 KB Output is correct
15 Correct 655 ms 4272 KB Output is correct
16 Correct 946 ms 4340 KB Output is correct
17 Correct 960 ms 4532 KB Output is correct
18 Correct 974 ms 4436 KB Output is correct
19 Correct 968 ms 4416 KB Output is correct
20 Correct 968 ms 4440 KB Output is correct
21 Execution timed out 2080 ms 6248 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 4300 KB Output is correct
2 Correct 139 ms 4432 KB Output is correct
3 Correct 149 ms 4448 KB Output is correct
4 Correct 160 ms 4624 KB Output is correct
5 Correct 172 ms 4372 KB Output is correct
6 Correct 219 ms 4344 KB Output is correct
7 Correct 225 ms 4304 KB Output is correct
8 Correct 222 ms 4304 KB Output is correct
9 Correct 222 ms 4284 KB Output is correct
10 Correct 224 ms 4308 KB Output is correct
11 Correct 150 ms 4352 KB Output is correct
12 Correct 123 ms 4380 KB Output is correct
13 Correct 125 ms 4316 KB Output is correct
14 Correct 136 ms 4428 KB Output is correct
15 Correct 151 ms 4396 KB Output is correct
16 Correct 160 ms 4332 KB Output is correct
17 Correct 146 ms 4300 KB Output is correct
18 Correct 157 ms 4408 KB Output is correct
19 Correct 150 ms 4320 KB Output is correct
20 Correct 167 ms 4300 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 4276 KB Output is correct
2 Correct 691 ms 4272 KB Output is correct
3 Correct 683 ms 4272 KB Output is correct
4 Correct 684 ms 4272 KB Output is correct
5 Correct 688 ms 4276 KB Output is correct
6 Correct 673 ms 4280 KB Output is correct
7 Correct 673 ms 4280 KB Output is correct
8 Correct 665 ms 4276 KB Output is correct
9 Correct 660 ms 4180 KB Output is correct
10 Correct 641 ms 4280 KB Output is correct
11 Correct 643 ms 4300 KB Output is correct
12 Correct 637 ms 4272 KB Output is correct
13 Correct 636 ms 4180 KB Output is correct
14 Correct 645 ms 4276 KB Output is correct
15 Correct 655 ms 4272 KB Output is correct
16 Correct 946 ms 4340 KB Output is correct
17 Correct 960 ms 4532 KB Output is correct
18 Correct 974 ms 4436 KB Output is correct
19 Correct 968 ms 4416 KB Output is correct
20 Correct 968 ms 4440 KB Output is correct
21 Execution timed out 2080 ms 6248 KB Time limit exceeded
22 Halted 0 ms 0 KB -