oj.uz

Submission #702975

# Submission time Handle Problem Language Result Execution time Memory
702975 2023-02-25T11:46:30 Z jhnah917 Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 373 ms 28712 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int K, Q, D, M, A[5050], Dst[5050];
vector<int> G[1010101];
unordered_map<ll, int> Vst, Prv;
inline ll Mod(ll t){ return (t % K + K) % K; }

void SmallBFS(){
    memset(Dst, -1, sizeof Dst);
    queue<ll> Que; Que.push(0); Dst[M] = 0; Vst[0] = 1;
    while(!Que.empty()){
        ll v = Que.front(); Que.pop();
        for(int i=1; i<=D; i++){
            ll nxt = v * K + A[i];
            if(abs(nxt) > M || Dst[nxt+M] != -1) continue;
            Que.push(nxt); Dst[nxt+M] = Dst[v+M] + 1;
            Vst[nxt] = 1; Prv[nxt] = A[i];
        }
    }
}

int Check(ll n){
    if(abs(n) <= M) return Dst[n+M] != -1;
    if(auto it=Vst.find(n); it != Vst.end()) return it->second;
    for(auto i : G[Mod(n)]) if(Check((n - A[i]) / K)) { Prv[n] = A[i]; return Vst[n] = 1; }
    return Vst[n] = 0;
}

vector<int> Path(ll n){
    vector<int> res;
    if(n != 0){
        if(!Check(n)) return {};
        while(n != 0) res.push_back(Prv[n]), n = (n - Prv[n]) / K;
        reverse(res.begin(), res.end());
        return res;
    }
    else{
        for(int i=1; i<=D; i++) if(A[i] == 0) return {A[i]};
        for(auto i : G[0]){
            if(!Check(-A[i] / K)) continue;
            res = Path(-A[i] / K); res.push_back(A[i]);
            return res;
        }
        return {};
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> K >> Q >> D >> M;
    for(int i=1; i<=D; i++) cin >> A[i], G[Mod(A[i])].push_back(i);
    SmallBFS();
    for(int q=1; q<=Q; q++){
        ll n; cin >> n;
        auto path = Path(n);
        if(path.empty()) cout << "IMPOSSIBLE\n";
        else for(int i=0; i<path.size(); i++) cout << path[i] << " \n"[i+1==path.size()];
    }
}

Compilation message

Main.cpp: In function 'int Check(ll)':
Main.cpp:26:8: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   26 |     if(auto it=Vst.find(n); it != Vst.end()) return it->second;
      |        ^~~~
Main.cpp: In function 'int main()':
Main.cpp:59:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         else for(int i=0; i<path.size(); i++) cout << path[i] << " \n"[i+1==path.size()];
      |                           ~^~~~~~~~~~~~
Main.cpp:59:75: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         else for(int i=0; i<path.size(); i++) cout << path[i] << " \n"[i+1==path.size()];
      |                                                                        ~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23984 KB OK
2 Correct 14 ms 24020 KB OK
3 Correct 12 ms 24020 KB OK
4 Correct 12 ms 24024 KB OK
5 Correct 16 ms 24072 KB OK
6 Correct 14 ms 24032 KB OK
7 Correct 15 ms 24020 KB OK
8 Correct 12 ms 23976 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23984 KB OK
2 Correct 14 ms 24020 KB OK
3 Correct 12 ms 24020 KB OK
4 Correct 12 ms 24024 KB OK
5 Correct 16 ms 24072 KB OK
6 Correct 14 ms 24032 KB OK
7 Correct 15 ms 24020 KB OK
8 Correct 12 ms 23976 KB OK
9 Correct 12 ms 24148 KB OK
10 Correct 13 ms 24092 KB OK
11 Correct 13 ms 24052 KB OK
12 Correct 12 ms 24148 KB OK
13 Correct 17 ms 24148 KB OK
14 Correct 13 ms 24088 KB OK
15 Correct 17 ms 24148 KB OK
16 Correct 12 ms 23984 KB OK
17 Correct 14 ms 24176 KB OK
18 Correct 13 ms 24048 KB OK
19 Correct 15 ms 24052 KB OK
20 Correct 12 ms 24052 KB OK
21 Correct 24 ms 24844 KB OK
22 Correct 87 ms 24788 KB OK
23 Correct 373 ms 28712 KB OK
24 Correct 157 ms 25620 KB OK
25 Correct 14 ms 24052 KB OK
26 Correct 14 ms 24148 KB OK
27 Correct 13 ms 24020 KB OK
28 Correct 12 ms 24020 KB OK