oj.uz

Submission #283109

# Submission time Handle Problem Language Result Execution time Memory
283109 2020-08-25T10:05:56 Z egekabas Brunhilda’s Birthday (BOI13_brunhilda) C++14
60.9524 / 100
 1000 ms 132016 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, q;
int p[100009];
vector<pii> ans;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    for(int i = 0; i < n; ++i)
        cin >> p[i];
    reverse(p, p+n);
    ans.pb({0, 0});
    while(1){
        int cur = ans.back().ff;
        int nxt = 0;
        for(int j = 0; j < n; ++j){
            nxt = max(nxt, cur - cur%p[j]+p[j]-1);
        }
        if(nxt <= cur)
            break;
        ans.pb({nxt, ans.back().ss+1});
    }
    while(q--){
        int x;
        cin >> x;
        int id = lower_bound(all(ans), mp(x, -1))-ans.begin();
        if(id == ans.size())
            cout << "oo\n";
        else
            cout << ans[id].ss << '\n';
    }
    
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(id == ans.size())
      |            ~~~^~~~~~~~~~~~~

Subtask #1
8.88888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Execution timed out 1091 ms 33400 KB Time limit exceeded
3 Correct 1 ms 512 KB Output is correct
4 Correct 426 ms 8768 KB Output is correct
5 Execution timed out 1094 ms 131928 KB Time limit exceeded
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Execution timed out 1093 ms 132016 KB Time limit exceeded
10 Execution timed out 1045 ms 66204 KB Time limit exceeded
11 Execution timed out 1084 ms 66492 KB Time limit exceeded
12 Correct 708 ms 8872 KB Output is correct
13 Execution timed out 1086 ms 1800 KB Time limit exceeded
14 Execution timed out 1097 ms 1560 KB Time limit exceeded
15 Execution timed out 1095 ms 33360 KB Time limit exceeded
16 Execution timed out 1097 ms 33352 KB Time limit exceeded
17 Execution timed out 1094 ms 33596 KB Time limit exceeded
18 Correct 423 ms 8680 KB Output is correct

Subtask #2
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 512 KB Output is correct
2 Correct 161 ms 1400 KB Output is correct
3 Correct 909 ms 1164 KB Output is correct
4 Correct 550 ms 760 KB Output is correct
5 Correct 627 ms 1272 KB Output is correct
6 Correct 271 ms 760 KB Output is correct
7 Correct 215 ms 512 KB Output is correct
8 Correct 622 ms 1648 KB Output is correct
9 Correct 869 ms 1324 KB Output is correct
10 Correct 906 ms 1144 KB Output is correct
11 Execution timed out 1098 ms 768 KB Time limit exceeded
12 Correct 770 ms 1016 KB Output is correct
13 Correct 98 ms 504 KB Output is correct
14 Correct 546 ms 944 KB Output is correct
15 Correct 853 ms 1096 KB Output is correct
16 Correct 163 ms 1280 KB Output is correct
17 Execution timed out 1080 ms 1176 KB Time limit exceeded
18 Correct 641 ms 1360 KB Output is correct

Subtask #3
34.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 1464 KB Output is correct
2 Execution timed out 1094 ms 1144 KB Time limit exceeded
3 Execution timed out 1054 ms 1144 KB Time limit exceeded
4 Correct 633 ms 1692 KB Output is correct
5 Correct 376 ms 2172 KB Output is correct
6 Execution timed out 1088 ms 1144 KB Time limit exceeded
7 Correct 684 ms 1760 KB Output is correct
8 Correct 832 ms 1352 KB Output is correct
9 Correct 840 ms 1400 KB Output is correct
10 Execution timed out 1051 ms 904 KB Time limit exceeded
11 Correct 780 ms 888 KB Output is correct
12 Execution timed out 1067 ms 888 KB Time limit exceeded
13 Correct 995 ms 1144 KB Output is correct
14 Execution timed out 1099 ms 33356 KB Time limit exceeded
15 Execution timed out 1091 ms 760 KB Time limit exceeded
16 Execution timed out 1089 ms 736 KB Time limit exceeded
17 Correct 948 ms 584 KB Output is correct
18 Execution timed out 1087 ms 856 KB Time limit exceeded
19 Correct 128 ms 504 KB Output is correct
20 Execution timed out 1060 ms 632 KB Time limit exceeded
21 Execution timed out 1044 ms 17040 KB Time limit exceeded
22 Execution timed out 1065 ms 1164 KB Time limit exceeded
23 Correct 499 ms 1024 KB Output is correct
24 Correct 226 ms 888 KB Output is correct
25 Execution timed out 1069 ms 1140 KB Time limit exceeded
26 Correct 621 ms 1048 KB Output is correct
27 Execution timed out 1058 ms 908 KB Time limit exceeded
28 Correct 192 ms 1020 KB Output is correct
29 Execution timed out 1080 ms 1020 KB Time limit exceeded
30 Execution timed out 1094 ms 640 KB Time limit exceeded
31 Correct 269 ms 760 KB Output is correct
32 Correct 608 ms 1012 KB Output is correct
33 Correct 128 ms 892 KB Output is correct
34 Correct 673 ms 888 KB Output is correct
35 Correct 315 ms 1020 KB Output is correct
36 Correct 967 ms 1020 KB Output is correct
37 Correct 364 ms 904 KB Output is correct
38 Execution timed out 1084 ms 892 KB Time limit exceeded
39 Correct 362 ms 888 KB Output is correct
40 Correct 825 ms 888 KB Output is correct
41 Correct 436 ms 888 KB Output is correct
42 Execution timed out 1046 ms 1300 KB Time limit exceeded