oj.uz

Submission #557292

# Submission time Handle Problem Language Result Execution time Memory
557292 2022-05-05T05:44:39 Z kwongweng Boat (APIO16_boat) C++17
36 / 100
 2000 ms 4300 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);
}

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
        ll val[i+2]; // val[i][j] = 
        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 = cnt[j+l[i]][k-1];
                ll binom = mul(interval - k + 1, inverse(k)) ; // 
                new_val = mul(new_val, binom);
                val[k] = new_val;
            }
            FOR(k,1,i+2){
                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:86:13: warning: unused variable 'num' [-Wunused-variable]
   86 |         int num = r[i]-l[i]; // # compartments
      |             ^~~
boat.cpp: In function 'int main()':
boat.cpp:119:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:120:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 4264 KB Output is correct
2 Correct 618 ms 4276 KB Output is correct
3 Correct 629 ms 4268 KB Output is correct
4 Correct 617 ms 4264 KB Output is correct
5 Correct 608 ms 4268 KB Output is correct
6 Correct 612 ms 4264 KB Output is correct
7 Correct 624 ms 4268 KB Output is correct
8 Correct 626 ms 4268 KB Output is correct
9 Correct 622 ms 4268 KB Output is correct
10 Correct 637 ms 4272 KB Output is correct
11 Correct 636 ms 4268 KB Output is correct
12 Correct 636 ms 4268 KB Output is correct
13 Correct 618 ms 4264 KB Output is correct
14 Correct 621 ms 4268 KB Output is correct
15 Correct 620 ms 4268 KB Output is correct
16 Correct 640 ms 4272 KB Output is correct
17 Correct 643 ms 4264 KB Output is correct
18 Correct 648 ms 4268 KB Output is correct
19 Correct 652 ms 4268 KB Output is correct
20 Correct 633 ms 4264 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 4264 KB Output is correct
2 Correct 618 ms 4276 KB Output is correct
3 Correct 629 ms 4268 KB Output is correct
4 Correct 617 ms 4264 KB Output is correct
5 Correct 608 ms 4268 KB Output is correct
6 Correct 612 ms 4264 KB Output is correct
7 Correct 624 ms 4268 KB Output is correct
8 Correct 626 ms 4268 KB Output is correct
9 Correct 622 ms 4268 KB Output is correct
10 Correct 637 ms 4272 KB Output is correct
11 Correct 636 ms 4268 KB Output is correct
12 Correct 636 ms 4268 KB Output is correct
13 Correct 618 ms 4264 KB Output is correct
14 Correct 621 ms 4268 KB Output is correct
15 Correct 620 ms 4268 KB Output is correct
16 Correct 640 ms 4272 KB Output is correct
17 Correct 643 ms 4264 KB Output is correct
18 Correct 648 ms 4268 KB Output is correct
19 Correct 652 ms 4268 KB Output is correct
20 Correct 633 ms 4264 KB Output is correct
21 Correct 1931 ms 4264 KB Output is correct
22 Correct 1871 ms 4280 KB Output is correct
23 Correct 1796 ms 4276 KB Output is correct
24 Correct 1924 ms 4272 KB Output is correct
25 Correct 1911 ms 4276 KB Output is correct
26 Execution timed out 2094 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4180 KB Output is correct
2 Correct 44 ms 4180 KB Output is correct
3 Correct 44 ms 4248 KB Output is correct
4 Correct 45 ms 4236 KB Output is correct
5 Correct 47 ms 4180 KB Output is correct
6 Correct 53 ms 4180 KB Output is correct
7 Correct 54 ms 4180 KB Output is correct
8 Correct 55 ms 4240 KB Output is correct
9 Correct 53 ms 4232 KB Output is correct
10 Correct 56 ms 4180 KB Output is correct
11 Correct 45 ms 4232 KB Output is correct
12 Correct 42 ms 4252 KB Output is correct
13 Correct 44 ms 4300 KB Output is correct
14 Correct 42 ms 4180 KB Output is correct
15 Correct 44 ms 4180 KB Output is correct
16 Correct 45 ms 4180 KB Output is correct
17 Correct 44 ms 4236 KB Output is correct
18 Correct 46 ms 4180 KB Output is correct
19 Correct 41 ms 4180 KB Output is correct
20 Correct 45 ms 4244 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 4264 KB Output is correct
2 Correct 618 ms 4276 KB Output is correct
3 Correct 629 ms 4268 KB Output is correct
4 Correct 617 ms 4264 KB Output is correct
5 Correct 608 ms 4268 KB Output is correct
6 Correct 612 ms 4264 KB Output is correct
7 Correct 624 ms 4268 KB Output is correct
8 Correct 626 ms 4268 KB Output is correct
9 Correct 622 ms 4268 KB Output is correct
10 Correct 637 ms 4272 KB Output is correct
11 Correct 636 ms 4268 KB Output is correct
12 Correct 636 ms 4268 KB Output is correct
13 Correct 618 ms 4264 KB Output is correct
14 Correct 621 ms 4268 KB Output is correct
15 Correct 620 ms 4268 KB Output is correct
16 Correct 640 ms 4272 KB Output is correct
17 Correct 643 ms 4264 KB Output is correct
18 Correct 648 ms 4268 KB Output is correct
19 Correct 652 ms 4268 KB Output is correct
20 Correct 633 ms 4264 KB Output is correct
21 Correct 1931 ms 4264 KB Output is correct
22 Correct 1871 ms 4280 KB Output is correct
23 Correct 1796 ms 4276 KB Output is correct
24 Correct 1924 ms 4272 KB Output is correct
25 Correct 1911 ms 4276 KB Output is correct
26 Execution timed out 2094 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -