oj.uz

Submission #738717

# Submission time Handle Problem Language Result Execution time Memory
738717 2023-05-09T12:59:14 Z Joshua_Andersson Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 495 ms 159316 KB 
#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define enablell 1

typedef long long ll;
typedef unsigned long long ull;
#if enablell
#define int ll
#define inf int(1e18)
#define float double
#else
const int inf = int(2e9);
#endif
typedef vector<ull> vull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<int, int> p2;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vvp2> vvvp2;
typedef tuple<int, int, int> p3;
typedef vector<p3> vp3;
typedef vector<vp3> vvp3;
typedef vector<vvp3> vvvp3;
typedef tuple<int, int, int, int> p4;
typedef vector<p4> vp4;

#define PBDS 0
#define _LOCAL _MSC_VER > 0
#if _LOCAL
#define gc() getchar()
#define popcount(x) __popcnt(x)
#define leading_zeros(x) _lzcnt_u32(x)
uint32_t clz(uint32_t x) { return _lzcnt_u32(x); }
uint32_t ctz(uint32_t x) { return _tzcnt_u32(x); }
#define bswap64(x) _byteswap_uint64(x)
#define assert(x) debassert(x)
#else
#define popcount(x) __builtin_popcount(x)
uint32_t clz(uint32_t x) { return __builtin_clz(x); }
uint32_t ctz(uint32_t x) { return __builtin_ctzll(x); }
#define bswap64(x) __builtin_bswap64(x)
#define gc() getchar_unlocked()
#if PBDS
using namespace __gnu_pbds;
// lower_bound is now upper_bound and vice versa (multiset). generally a bit broken
template<typename T> using indexed_multiset = tree<int, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct chash { // large odd number for C
    const uint64_t C = ll(4e18 * acos(0)) | 71;
    ll operator()(ll x) const { return __builtin_bswap64(x * C); }
};

template<typename T, typename U> using fast_map = __gnu_pbds::gp_hash_table<T, U, chash>;
template<typename T> using fast_set = __gnu_pbds::gp_hash_table<T, null_type, chash>;
template<typename T, typename H> using fast_set_h = __gnu_pbds::gp_hash_table<T, null_type, H>;
#endif

#endif

#define FAST_INPUT 0
#define FILE_TC 0
#if FILE_TC && _LOCAL
//ifstream filein("E:\\desktop\\code\\repos\\Comp prog\\x64\\Debug\\in.txt");
ifstream filein("C:\\users\\matis\\source\\repos\\Comp Prog\\x64\\Debug\\1.in");
//ifstream filein("E:\\downloads\\test_data\\test_data\\005-case05.in");
//ifstream filein("E:\\desktop\\po-repos\\swedish-olympiad-2023\\online\\tomtplanering\\data\\secret\\group10\\010-case10.in");

#define cin filein
void fast() {}
#else
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#endif

#if FAST_INPUT && !FILE_TC
inline void read(int& v) { v = 0; int sign = 1; char c = gc(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = gc()) && c != ' ' && c != '\n') { if (c == EOF) { v = -1; return; } v *= 10; v += c - '0'; } v *= sign; }
inline void read(int& u, int& v) { read(u); read(v); }
inline void read(int& u, int& v, int& k) { read(u); read(v); read(k); }
//inline void read(int& v) { char c; while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } }
inline void read(string& s) { char c; while ((c = gc()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } }
inline void readline(string& s) { char c; while ((c = gc()) != EOF && c != '\n') { s.push_back(c); } }
#else
template <typename T> inline void read(T& a) { cin >> a; }
template <typename T> inline void read(T& a, T& b) { cin >> a >> b; }
template <typename T> inline void read(T& a, T& b, T& c) { cin >> a >> b >> c; }
#endif
#define quit cout << endl; _Exit(0);
#define dread(type, a) type a; read(a)
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#ifdef _DEBUG
#define noop cout << "";
#define deb __debugbreak();
#define debassert(expr) if(!(expr)) deb;
#define debif(expr) if(expr) deb;
#else
#define noop ;
#define deb ;
#define debif(expr) ;
#define debassert(expr) ;
#endif

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)
#define perr(i, low, high) for (int i = high-1; i >= low; i--)

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define within(a, b, c, d) (a >= 0 && a < b && c >= 0 && c < d)
#define sz(container) ((int)container.size())
#define mp(a,b) (make_pair(a,b))

#define ceildiv(x,y) ((x + y - 1) / y)

template <typename T, typename U> inline void operator+=(pair<T, U>& l, const pair<T, U>& r) { l = { l.first + r.first,l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator+(const pair<T, U> l, const pair<T, U> r) { return { l.first + r.first, l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator-(const pair<T, U> l, const pair<T, U> r) { return { l.first - r.first, l.second - r.second }; }
template <typename T, typename U> inline pair<T, U> operator*(const pair<T, U> l, const int m) { return { l.first * m, l.second * m }; }
template <typename Out> inline void split(const string& s, char delim, Out result) { istringstream iss(s); string item; while (getline(iss, item, delim)) { *result++ = item; } }
inline vector<string> split(const string& s, char delim) { vector<string> elems; split(s, delim, back_inserter(elems)); return elems; }
vector<string> split(string s, string d) { size_t k = 0, n, e = d.length(); string t; vector<string> r; while ((n = s.find(d, k)) != string::npos) { t = s.substr(k, n - k); k = n + e; r.push_back(t); } r.push_back(s.substr(k)); return r; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } // For a < 2^31

#if 1
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]
#endif
const ll mod = 1e9 + 7;
vp2 dirs = { {0,1},{0,-1},{1,0},{-1,0}, {0,0} };



int32_t main()
{
    fast();

    dread2(int, n, q);
    readvector(int, nums, n);


    const int hi = 2e7;

    vi dp(hi, 0);
    repe(num, nums)
    {
        for (int i = num - 1; i < dp.size(); i += num)
        {
            dp[i] = max(dp[i], num - 1);
        }
    }

    for (int i = dp.size() - 2; i >= 0; i--)
    {
        dp[i] = max(dp[i], dp[i + 1] - 1);
    }

    dp[0] = 0;


    repp(i, 1, hi)
    {
        if (dp[i] == 0) dp[i] = inf;
        else dp[i] = dp[max(0LL, i - dp[i])] + 1;
    }

    rep(i, q)
    {
        dread(int, v);
        if (dp[v] >= inf) cout << "oo\n";
        else cout << dp[v] << "\n";
    }


    quit;
}

Compilation message

brunhilda.cpp: In function 'int32_t main()':
brunhilda.cpp:174:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         for (int i = num - 1; i < dp.size(); i += num)
      |                               ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 156880 KB Output is correct
2 Correct 166 ms 156800 KB Output is correct
3 Correct 164 ms 156808 KB Output is correct
4 Correct 114 ms 156876 KB Output is correct
5 Correct 160 ms 156868 KB Output is correct
6 Correct 138 ms 156776 KB Output is correct
7 Correct 156 ms 157004 KB Output is correct
8 Correct 168 ms 156840 KB Output is correct
9 Correct 205 ms 156884 KB Output is correct
10 Correct 251 ms 156872 KB Output is correct
11 Correct 211 ms 156916 KB Output is correct
12 Correct 108 ms 156876 KB Output is correct
13 Correct 396 ms 156800 KB Output is correct
14 Correct 360 ms 156932 KB Output is correct
15 Correct 176 ms 156880 KB Output is correct
16 Correct 163 ms 156892 KB Output is correct
17 Correct 151 ms 156928 KB Output is correct
18 Correct 112 ms 156876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 156944 KB Output is correct
2 Correct 151 ms 158180 KB Output is correct
3 Correct 452 ms 157816 KB Output is correct
4 Correct 179 ms 156840 KB Output is correct
5 Correct 295 ms 157672 KB Output is correct
6 Correct 159 ms 156948 KB Output is correct
7 Correct 136 ms 157132 KB Output is correct
8 Correct 175 ms 156896 KB Output is correct
9 Correct 352 ms 157904 KB Output is correct
10 Correct 450 ms 157904 KB Output is correct
11 Correct 471 ms 157460 KB Output is correct
12 Correct 241 ms 156956 KB Output is correct
13 Correct 133 ms 156876 KB Output is correct
14 Correct 172 ms 156876 KB Output is correct
15 Correct 373 ms 157536 KB Output is correct
16 Correct 167 ms 158304 KB Output is correct
17 Correct 370 ms 156920 KB Output is correct
18 Correct 352 ms 158388 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 157952 KB Output is correct
2 Correct 446 ms 157840 KB Output is correct
3 Correct 466 ms 158204 KB Output is correct
4 Correct 285 ms 157772 KB Output is correct
5 Correct 190 ms 159308 KB Output is correct
6 Correct 373 ms 157956 KB Output is correct
7 Correct 308 ms 158864 KB Output is correct
8 Correct 387 ms 157896 KB Output is correct
9 Correct 370 ms 157956 KB Output is correct
10 Correct 286 ms 157080 KB Output is correct
11 Correct 232 ms 157156 KB Output is correct
12 Correct 338 ms 157168 KB Output is correct
13 Correct 417 ms 158272 KB Output is correct
14 Correct 256 ms 158156 KB Output is correct
15 Correct 358 ms 157268 KB Output is correct
16 Correct 404 ms 157148 KB Output is correct
17 Correct 338 ms 157620 KB Output is correct
18 Correct 445 ms 157860 KB Output is correct
19 Correct 154 ms 157164 KB Output is correct
20 Correct 492 ms 158252 KB Output is correct
21 Correct 314 ms 158172 KB Output is correct
22 Correct 478 ms 159316 KB Output is correct
23 Correct 188 ms 158280 KB Output is correct
24 Correct 160 ms 157836 KB Output is correct
25 Correct 301 ms 157912 KB Output is correct
26 Correct 272 ms 157788 KB Output is correct
27 Correct 495 ms 158804 KB Output is correct
28 Correct 168 ms 157856 KB Output is correct
29 Correct 412 ms 159268 KB Output is correct
30 Correct 411 ms 158832 KB Output is correct
31 Correct 188 ms 157892 KB Output is correct
32 Correct 210 ms 157908 KB Output is correct
33 Correct 147 ms 157832 KB Output is correct
34 Correct 293 ms 158928 KB Output is correct
35 Correct 171 ms 157900 KB Output is correct
36 Correct 436 ms 159184 KB Output is correct
37 Correct 183 ms 159308 KB Output is correct
38 Correct 360 ms 157948 KB Output is correct
39 Correct 167 ms 157936 KB Output is correct
40 Correct 321 ms 157948 KB Output is correct
41 Correct 289 ms 158928 KB Output is correct
42 Correct 403 ms 158152 KB Output is correct