Submission #702963

#	Time	Username	Problem	Language	Result	Execution time	Memory
702963		jhnah917	Weird Numeral System (CCO21_day1problem2)	C++14	0 / 25	13 ms	23956 KiB

Main

#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 int Mod(ll t){ return (t %= K) >= 0 ? t : t + K; }

void SmallBFS(){
    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.find(nxt) != Vst.end()) continue;
            Que.push(nxt); Vst[nxt] = 1; Prv[nxt] = A[i];
        }
    }
}

bool 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{
        if(find(A+1, A+D+1, 0) - A <= D) return {0};
        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";
        else for(auto i : path) cout << i << " ";
        cout << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'bool Check(ll)':
Main.cpp:23:8: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   23 |     if(auto it=Vst.find(n); it != Vst.end()) return it->second;
      |        ^~~~
Main.cpp:24:86: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |     for(auto i : G[Mod(n)]) if(Check((n - A[i]) / K)) { Prv[n] = A[i]; return Vst[n] = 1; }
Main.cpp:25:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |     return Vst[n] = 0;

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17