oj.uz

Submission #702977

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

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

void SmallBFS(){
    for(int i=-M; i<=M; i++) Vst[i] = 0;
    queue<ll> Que; Que.push(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 || Vst[nxt]) continue;
            Que.push(nxt); Vst[nxt] = 1; Prv[nxt] = A[i];
        }
    }
}

int Check(ll n){
    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:24:8: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   24 |     if(auto it=Vst.find(n); it != Vst.end()) return it->second;
      |        ^~~~
Main.cpp: In function 'int main()':
Main.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         else for(int i=0; i<path.size(); i++) cout << path[i] << " \n"[i+1==path.size()];
      |                           ~^~~~~~~~~~~~
Main.cpp:57:75: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         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 12 ms 24020 KB OK
2 Correct 13 ms 24048 KB OK
3 Correct 15 ms 24052 KB OK
4 Correct 15 ms 24040 KB OK
5 Correct 13 ms 24024 KB OK
6 Correct 13 ms 24004 KB OK
7 Correct 13 ms 24020 KB OK
8 Correct 13 ms 24020 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24020 KB OK
2 Correct 13 ms 24048 KB OK
3 Correct 15 ms 24052 KB OK
4 Correct 15 ms 24040 KB OK
5 Correct 13 ms 24024 KB OK
6 Correct 13 ms 24004 KB OK
7 Correct 13 ms 24020 KB OK
8 Correct 13 ms 24020 KB OK
9 Correct 16 ms 24036 KB OK
10 Correct 13 ms 24068 KB OK
11 Correct 13 ms 24024 KB OK
12 Correct 14 ms 24120 KB OK
13 Correct 14 ms 24020 KB OK
14 Correct 13 ms 24128 KB OK
15 Correct 13 ms 24020 KB OK
16 Correct 13 ms 24020 KB OK
17 Correct 14 ms 24148 KB OK
18 Correct 15 ms 24020 KB OK
19 Correct 21 ms 24140 KB OK
20 Correct 13 ms 24020 KB OK
21 Correct 23 ms 24788 KB OK
22 Correct 84 ms 25156 KB OK
23 Correct 355 ms 28696 KB OK
24 Correct 156 ms 25640 KB OK
25 Correct 15 ms 24020 KB OK
26 Correct 15 ms 24020 KB OK
27 Correct 13 ms 24044 KB OK
28 Correct 13 ms 24020 KB OK