oj.uz

Submission #1102360

# Submission time Handle Problem Language Result Execution time Memory
1102360 2024-10-18T03:09:13 Z vjudge1 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1124 ms 23888 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;

void solve() {
    int k, q, d, m;
    cin >> k >> q >> d >> m;

    auto gmod = [&](int val) -> int {
        int res = val % k;
        return (res < 0 ? res + k : res);
    };

    vector<int> a(d);
    vector<vector<int>> md(k);
    for (auto &val : a) {
        cin >> val;
        md[gmod(val)].emplace_back(val);
    }

    vector<int> vec;
    map<int, int> mp;   
    auto dfs = [&](auto self, int val) -> bool {
        if (mp.count(val)) return false;
        mp[val] = false;
        for (auto coef : md[gmod(val)]) {
            if (coef == val) {
                vec.emplace_back(coef);
                return true;
            }
            if ((val - coef) / k != val and self(self, (val - coef) / k)) {
                vec.emplace_back(coef);
                return true;
            }
        }
        return false;
    };

    while (q--) {
        int n;
        cin >> n;
        mp.clear();
        vec.clear();
        if (!dfs(dfs, n)) {
            cout << "IMPOSSIBLE" << "\n";
        }
        else {
            for (int i = 0; i < isz(vec); ++i) {
                cout << vec[i] << " \n"[i + 1 == isz(vec)];
            }
        }
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK
2 Correct 1 ms 504 KB OK
3 Correct 1 ms 592 KB OK
4 Correct 1 ms 336 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 560 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK
2 Correct 1 ms 504 KB OK
3 Correct 1 ms 592 KB OK
4 Correct 1 ms 336 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 560 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK
9 Correct 1 ms 336 KB OK
10 Correct 1 ms 336 KB OK
11 Correct 1 ms 336 KB OK
12 Correct 1 ms 336 KB OK
13 Correct 1 ms 336 KB OK
14 Correct 1 ms 336 KB OK
15 Correct 1 ms 336 KB OK
16 Correct 1 ms 336 KB OK
17 Correct 5 ms 23888 KB OK
18 Correct 1 ms 336 KB OK
19 Correct 1 ms 336 KB OK
20 Correct 1 ms 336 KB OK
21 Correct 38 ms 1596 KB OK
22 Correct 234 ms 1616 KB OK
23 Correct 1124 ms 1528 KB OK
24 Correct 480 ms 1608 KB OK
25 Correct 1 ms 336 KB OK
26 Correct 1 ms 336 KB OK
27 Correct 1 ms 336 KB OK
28 Correct 1 ms 336 KB OK