oj.uz

Submission #800821

# Submission time Handle Problem Language Result Execution time Memory
800821 2023-08-01T22:23:55 Z nnhzzz Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 239 ms 158540 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>

using namespace std;

#define    SORT_UNIQUE(v)  sort(ALL(v)),(v).resize(unique(ALL(v))-(v).begin())
#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define           RALL(x)  (x).rbegin(),(x).rend()
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define               INF  0x3f3f3f3f
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define             vvvvi  vector<vvvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define      RESET(x,val)  memset((x),(val),sizeof(x))
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define               int  ll
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 1e7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int f[MAXN+3],dp[MAXN+3];

void solve(){
    int n,m; cin >> n >> m;
    REP(i,1,n){
        int val; cin >> val;
        REPDIS(j,val,MAXN,val){
            f[j-1] = val-1;
        }
        f[MAXN] = max(f[MAXN],MAXN%val);
    }
    REPD(i,MAXN-1,1){
        f[i] = max(f[i],f[i+1]-1);
    }
    REP(i,1,MAXN){
        if(dp[i-f[i]]==-1 || f[i]==0){
            dp[i] = -1;
        }else{
            dp[i] = dp[i-f[i]]+1;
        }
    }
    while(m--){
        int pos; cin >> pos;
        if(dp[pos]==-1){
            cout << "oo";
        }else{
            cout << dp[pos];
        }
        cout << "\n";
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 156876 KB Output is correct
2 Correct 88 ms 156804 KB Output is correct
3 Correct 85 ms 156748 KB Output is correct
4 Correct 76 ms 156840 KB Output is correct
5 Correct 85 ms 156800 KB Output is correct
6 Correct 75 ms 156876 KB Output is correct
7 Correct 85 ms 156868 KB Output is correct
8 Correct 93 ms 156804 KB Output is correct
9 Correct 109 ms 156804 KB Output is correct
10 Correct 115 ms 156804 KB Output is correct
11 Correct 105 ms 156808 KB Output is correct
12 Correct 74 ms 156824 KB Output is correct
13 Correct 175 ms 156840 KB Output is correct
14 Correct 165 ms 156880 KB Output is correct
15 Correct 94 ms 156848 KB Output is correct
16 Correct 87 ms 156796 KB Output is correct
17 Correct 93 ms 156876 KB Output is correct
18 Correct 76 ms 156912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 156844 KB Output is correct
2 Correct 104 ms 157468 KB Output is correct
3 Correct 202 ms 157256 KB Output is correct
4 Correct 99 ms 156820 KB Output is correct
5 Correct 159 ms 157160 KB Output is correct
6 Correct 96 ms 156784 KB Output is correct
7 Correct 84 ms 156876 KB Output is correct
8 Correct 92 ms 156808 KB Output is correct
9 Correct 174 ms 157280 KB Output is correct
10 Correct 205 ms 157232 KB Output is correct
11 Correct 192 ms 157100 KB Output is correct
12 Correct 119 ms 156808 KB Output is correct
13 Correct 79 ms 156840 KB Output is correct
14 Correct 96 ms 156876 KB Output is correct
15 Correct 217 ms 157080 KB Output is correct
16 Correct 101 ms 157548 KB Output is correct
17 Correct 171 ms 156884 KB Output is correct
18 Correct 168 ms 157544 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 157524 KB Output is correct
2 Correct 221 ms 157356 KB Output is correct
3 Correct 209 ms 157700 KB Output is correct
4 Correct 148 ms 157760 KB Output is correct
5 Correct 137 ms 158540 KB Output is correct
6 Correct 185 ms 157872 KB Output is correct
7 Correct 161 ms 158140 KB Output is correct
8 Correct 182 ms 157504 KB Output is correct
9 Correct 187 ms 157548 KB Output is correct
10 Correct 138 ms 156976 KB Output is correct
11 Correct 120 ms 157104 KB Output is correct
12 Correct 163 ms 157088 KB Output is correct
13 Correct 196 ms 157944 KB Output is correct
14 Correct 130 ms 158156 KB Output is correct
15 Correct 189 ms 157148 KB Output is correct
16 Correct 182 ms 157116 KB Output is correct
17 Correct 161 ms 157208 KB Output is correct
18 Correct 208 ms 157384 KB Output is correct
19 Correct 88 ms 157000 KB Output is correct
20 Correct 223 ms 157772 KB Output is correct
21 Correct 147 ms 158252 KB Output is correct
22 Correct 228 ms 158512 KB Output is correct
23 Correct 119 ms 158068 KB Output is correct
24 Correct 103 ms 157820 KB Output is correct
25 Correct 156 ms 157896 KB Output is correct
26 Correct 162 ms 157744 KB Output is correct
27 Correct 239 ms 158092 KB Output is correct
28 Correct 111 ms 157872 KB Output is correct
29 Correct 208 ms 158520 KB Output is correct
30 Correct 195 ms 158232 KB Output is correct
31 Correct 114 ms 157696 KB Output is correct
32 Correct 131 ms 157808 KB Output is correct
33 Correct 97 ms 157740 KB Output is correct
34 Correct 174 ms 158068 KB Output is correct
35 Correct 110 ms 157900 KB Output is correct
36 Correct 222 ms 158388 KB Output is correct
37 Correct 121 ms 158540 KB Output is correct
38 Correct 186 ms 157820 KB Output is correct
39 Correct 124 ms 157928 KB Output is correct
40 Correct 161 ms 157872 KB Output is correct
41 Correct 149 ms 158064 KB Output is correct
42 Correct 193 ms 158028 KB Output is correct