oj.uz

Submission #968949

# Submission time Handle Problem Language Result Execution time Memory
968949 2024-04-24T10:08:51 Z Mher777 Brunhilda’s Birthday (BOI13_brunhilda) C++17
77.4603 / 100
 268 ms 79956 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

/* -------------------- Functions -------------------- */

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void precision(int x) {
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}

ll gcd(ll a, ll b) {
    if (a == 0 || b == 0) return(max(a, b));
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll range_sum(ll a, ll b) {
    if (a > b) return 0ll;
    ll dif = a - 1, cnt = b - a + 1;
    ll ans = ((b - a + 1) * (b - a + 2)) / 2;
    ans += ((b - a + 1) * dif);
    return ans;
}

string dec_to_bin(ll a) {
    string s = "";
    for (ll i = a; i > 0; ) {
        ll k = i % 2;
        i /= 2;
        char c = k + 48;
        s += c;
    }
    if (a == 0) {
        s = "0";
    }
    reverse(all(s));
    return s;
}

ll bin_to_dec(string s) {
    ll num = 0;
    for (int i = 0; i < s.size(); i++) {
        num *= 2ll;
        num += (s[i] - '0');
    }
    return num;
}

ll factorial_by_mod(ll n, ll mod) {
    ll ans = 1;
    ll num;
    for (ll i = 1; i <= n; ++i) {
        num = i % mod;
        ans *= num;
        ans %= mod;
    }
    return ans;
}

int isPrime(ll a) {
    if (a == 1) return 0;
    for (ll i = 2; i * i <= a; i++) {
        if (a % i == 0) return 0;
    }
    return 1;
}

ll binpow(ll a, ll b) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

/* -------------------- Solution -------------------- */

const int N = 10000005;
int mx[N], ans[N];

void slv() {
    int n, q;
    cin >> n >> q;
    vi v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    v.erase(unique(all(v)), v.end());
    sort(all(v));
    for (auto elem : v) {
        for (int i = elem - 1; i <= N - 5; i += elem) {
            mx[i] = max(mx[i], elem - 1);
        }
    }
    for (int i = N - 5; i >= 1; --i) {
        mx[i] = max(mx[i], mx[i + 1] - 1);
    }
    for (int i = 1; i <= N - 5; ++i) {
        if (mx[i] == 0) {
            ans[i] = -1;
            continue;
        }
        ans[i] = ans[i - mx[i]];
        if (ans[i] != -1) ++ans[i];
    }
    while (q--) {
        int x;
        cin >> x;
        if (ans[x] == -1) {
            cout << "oo" << '\n';
        }
        else {
            cout << ans[x] << '\n';
        }
    }
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    //precision(0);
    cs();
    return 0;
}

Compilation message

brunhilda.cpp: In function 'll range_sum(ll, ll)':
brunhilda.cpp:97:21: warning: unused variable 'cnt' [-Wunused-variable]
   97 |     ll dif = a - 1, cnt = b - a + 1;
      |                     ^~~
brunhilda.cpp: In function 'll bin_to_dec(std::string)':
brunhilda.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 78520 KB Output is correct
2 Correct 88 ms 78500 KB Output is correct
3 Correct 78 ms 78672 KB Output is correct
4 Correct 72 ms 78668 KB Output is correct
5 Correct 77 ms 78496 KB Output is correct
6 Correct 72 ms 78680 KB Output is correct
7 Correct 81 ms 78496 KB Output is correct
8 Correct 90 ms 78496 KB Output is correct
9 Correct 98 ms 78500 KB Output is correct
10 Correct 101 ms 78516 KB Output is correct
11 Correct 96 ms 78640 KB Output is correct
12 Correct 69 ms 78512 KB Output is correct
13 Correct 157 ms 78708 KB Output is correct
14 Correct 157 ms 78676 KB Output is correct
15 Correct 86 ms 78476 KB Output is correct
16 Correct 84 ms 78504 KB Output is correct
17 Correct 81 ms 78672 KB Output is correct
18 Correct 69 ms 78700 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 78548 KB Output is correct
2 Correct 92 ms 78872 KB Output is correct
3 Correct 193 ms 78780 KB Output is correct
4 Correct 92 ms 78676 KB Output is correct
5 Correct 133 ms 78728 KB Output is correct
6 Correct 106 ms 78524 KB Output is correct
7 Correct 92 ms 78544 KB Output is correct
8 Correct 100 ms 78504 KB Output is correct
9 Correct 153 ms 78804 KB Output is correct
10 Correct 185 ms 78932 KB Output is correct
11 Incorrect 194 ms 78672 KB Output isn't correct
12 Correct 116 ms 78512 KB Output is correct
13 Correct 78 ms 78516 KB Output is correct
14 Correct 100 ms 78672 KB Output is correct
15 Correct 160 ms 78840 KB Output is correct
16 Correct 100 ms 78932 KB Output is correct
17 Correct 170 ms 78680 KB Output is correct
18 Correct 168 ms 78920 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 78972 KB Output is correct
2 Correct 215 ms 78984 KB Output is correct
3 Correct 246 ms 79188 KB Output is correct
4 Incorrect 139 ms 79468 KB Output isn't correct
5 Incorrect 117 ms 79932 KB Output isn't correct
6 Correct 173 ms 79484 KB Output is correct
7 Correct 194 ms 79364 KB Output is correct
8 Correct 176 ms 78972 KB Output is correct
9 Correct 170 ms 78972 KB Output is correct
10 Correct 131 ms 78676 KB Output is correct
11 Incorrect 134 ms 78672 KB Output isn't correct
12 Correct 141 ms 78676 KB Output is correct
13 Correct 208 ms 79444 KB Output is correct
14 Correct 120 ms 79956 KB Output is correct
15 Incorrect 156 ms 78932 KB Output isn't correct
16 Correct 186 ms 78856 KB Output is correct
17 Correct 162 ms 78928 KB Output is correct
18 Correct 205 ms 78928 KB Output is correct
19 Incorrect 82 ms 78780 KB Output isn't correct
20 Correct 192 ms 79220 KB Output is correct
21 Incorrect 138 ms 79932 KB Output isn't correct
22 Correct 268 ms 79956 KB Output is correct
23 Correct 109 ms 79444 KB Output is correct
24 Correct 94 ms 79556 KB Output is correct
25 Incorrect 153 ms 79580 KB Output isn't correct
26 Incorrect 143 ms 79540 KB Output isn't correct
27 Correct 244 ms 79388 KB Output is correct
28 Incorrect 96 ms 79700 KB Output isn't correct
29 Correct 192 ms 79904 KB Output is correct
30 Correct 199 ms 79660 KB Output is correct
31 Correct 118 ms 79188 KB Output is correct
32 Incorrect 115 ms 79444 KB Output isn't correct
33 Incorrect 92 ms 79188 KB Output isn't correct
34 Correct 148 ms 79440 KB Output is correct
35 Incorrect 103 ms 79696 KB Output isn't correct
36 Correct 232 ms 79884 KB Output is correct
37 Incorrect 107 ms 79924 KB Output isn't correct
38 Correct 174 ms 79296 KB Output is correct
39 Incorrect 107 ms 79696 KB Output isn't correct
40 Correct 154 ms 79444 KB Output is correct
41 Correct 133 ms 79188 KB Output is correct
42 Incorrect 180 ms 79800 KB Output isn't correct