oj.uz

Submission #411672

# Submission time Handle Problem Language Result Execution time Memory
411672 2021-05-25T17:35:44 Z Plasmatic Weird Numeral System (CCO21_day1problem2) C++11
25 / 25
 1963 ms 88648 KB 
// ./cco-21-p2-weird-numeral-system.yml
#include "bits/stdc++.h"
using namespace std;

// Defines
#define fs first
#define sn second
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
// Basic type definitions
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<long long, long long>;
#ifdef __GNUG__
// PBDS order statistic tree
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>;
// HashSet
#include <ext/pb_ds/assoc_container.hpp>
template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>;
template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash { ll operator()(ll x) const { return x ^ RANDOM; } };
#endif
// More utilities
int SZ(string &v) { return v.length(); }
template <typename C> int SZ(C &v) { return v.size(); }
template <typename C> void UNIQUE(vector<C> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); }
template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); }
template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); }
const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f;

const pair<int, ll> BAD = {INF, LLINF};
const int MK = 1e6+1, SHF = 2e6+1;
int K, Q, D, M;
vector<int> md[MK];

unordered_map<ll, pair<int, ll>> par;
pair<int, ll> par2[SHF*2+5];

bool has(ll n) {
    if (abs(n) <= SHF) return par2[n+SHF] != BAD;
    return par.count(n);
}
void save(ll n, int d, ll p) {
    if (abs(n) <= SHF) par2[n+SHF] = {d, p};
    par[n] = {d, p};
}
pair<int, ll> get(ll n) {
    if (abs(n) <= SHF) return par2[n+SHF];
    return par[n];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> K >> Q >> D >> M;
    for (auto i = 0; i < D; i++) {
        int x; cin >> x;
        md[((x%K)+K)%K].pb(x);
    }

    while (Q--) {
        ll n; cin >> n;

        par.clear();
        fill(par2, par2+SHF*2+5, BAD);

        ll st = n ? n : LLINF;
        queue<ll> q; q.push(st); save(st, -1, -1);
        while (!q.empty()) {
            auto n = q.front(); q.pop();
            if (n == 0) break;
            ll tv = n == LLINF ? 0 : n;
            for (auto d : md[((tv%K)+K)%K]) {
                ll alt = (tv-d)/K;
                if (!has(alt)) {
                    save(alt, d, n);
                    q.push(alt);
                }
            }
        }

        if (has(0)) {
            vector<int> ans;
            for (ll cur = 0; cur != st; cur = get(cur).second)
                ans.push_back(get(cur).first);
            for (auto i = 0; i < SZ(ans); i++) cout << ans[i] << " \n"[i == SZ(ans)-1];
        }
        else
            cout << ("IMPOSSIBLE") << '\n';
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 86340 KB OK
2 Correct 78 ms 86340 KB OK
3 Correct 80 ms 86320 KB OK
4 Correct 78 ms 86340 KB OK
5 Correct 81 ms 86396 KB OK
6 Correct 84 ms 86348 KB OK
7 Correct 79 ms 86400 KB OK
8 Correct 84 ms 86380 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 86340 KB OK
2 Correct 78 ms 86340 KB OK
3 Correct 80 ms 86320 KB OK
4 Correct 78 ms 86340 KB OK
5 Correct 81 ms 86396 KB OK
6 Correct 84 ms 86348 KB OK
7 Correct 79 ms 86400 KB OK
8 Correct 84 ms 86380 KB OK
9 Correct 95 ms 87880 KB OK
10 Correct 100 ms 86976 KB OK
11 Correct 81 ms 86552 KB OK
12 Correct 80 ms 86564 KB OK
13 Correct 187 ms 88428 KB OK
14 Correct 106 ms 87124 KB OK
15 Correct 88 ms 86800 KB OK
16 Correct 79 ms 86352 KB OK
17 Correct 79 ms 86420 KB OK
18 Correct 1212 ms 88576 KB OK
19 Correct 1963 ms 88560 KB OK
20 Correct 80 ms 86348 KB OK
21 Correct 130 ms 87508 KB OK
22 Correct 448 ms 87412 KB OK
23 Correct 626 ms 87620 KB OK
24 Correct 441 ms 87504 KB OK
25 Correct 733 ms 88460 KB OK
26 Correct 858 ms 88648 KB OK
27 Correct 63 ms 86392 KB OK
28 Correct 46 ms 86344 KB OK