Submission #702975

#	Time	Username	Problem	Language	Result	Execution time	Memory
702975		jhnah917	Weird Numeral System (CCO21_day1problem2)	C++14	25 / 25	373 ms	28712 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 17 / 17