oj.uz

Submission #635760

# Submission time Handle Problem Language Result Execution time Memory
635760 2022-08-26T19:05:45 Z jhnah917 Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 1622 ms 6320 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
constexpr int X = 2500;

int K, Q, N, M, A[5050], D[5050], P[5050];
map<ll, int> Chk, Prv;

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

int DFS(ll n){
    auto it = Chk.find(n); if(it != Chk.end()) return it->second;
    if(abs(n) <= M) return Chk[n] = D[n+X] != -1;
    for(int i=1; i<=N; i++){
        if((n - A[i]) % K == 0 && DFS((n - A[i]) / K)){
            Prv[n] = A[i]; return Chk[n] = 1;
        }
    }
    return Chk[n] = 0;
}

vector<int> Track(ll n){
    vector<int> res;
    while(n != 0){
        int now = abs(n) <= M ? P[n+X] : Prv[n];
        res.push_back(now);
        n = (n - now) / K;
    }
    reverse(res.begin(), res.end());
    return res;
}

void Zero(){
    for(int i=1; i<=N; i++){
        if(A[i] % K != 0 || !DFS(-A[i] / K)) continue;
        vector<int> vec = Track(-A[i] / K); vec.push_back(A[i]);
        for(int j=0; j<vec.size(); j++) cout << vec[j] << " \n"[j+1==vec.size()];
        return;
    }
    cout << "IMPOSSIBLE\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> K >> Q >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    BFS();
    for(int q=1; q<=Q; q++){
        ll n; cin >> n;
        if(n == 0){ Zero(); continue; }
        if(!DFS(n)){ cout << "IMPOSSIBLE\n"; continue; }
        auto vec = Track(n);
        for(int i=0; i<vec.size(); i++) cout << vec[i] << " \n"[i+1==vec.size()];
    }
}

Compilation message

Main.cpp: In function 'void Zero()':
Main.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j=0; j<vec.size(); j++) cout << vec[j] << " \n"[j+1==vec.size()];
      |                      ~^~~~~~~~~~~
Main.cpp:51:68: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j=0; j<vec.size(); j++) cout << vec[j] << " \n"[j+1==vec.size()];
      |                                                                 ~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0; i<vec.size(); i++) cout << vec[i] << " \n"[i+1==vec.size()];
      |                      ~^~~~~~~~~~~
Main.cpp:67:68: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0; i<vec.size(); i++) cout << vec[i] << " \n"[i+1==vec.size()];
      |                                                                 ~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK
2 Correct 0 ms 340 KB OK
3 Correct 1 ms 340 KB OK
4 Correct 1 ms 340 KB OK
5 Correct 1 ms 340 KB OK
6 Correct 1 ms 340 KB OK
7 Correct 0 ms 340 KB OK
8 Correct 1 ms 340 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK
2 Correct 0 ms 340 KB OK
3 Correct 1 ms 340 KB OK
4 Correct 1 ms 340 KB OK
5 Correct 1 ms 340 KB OK
6 Correct 1 ms 340 KB OK
7 Correct 0 ms 340 KB OK
8 Correct 1 ms 340 KB OK
9 Correct 1 ms 384 KB OK
10 Correct 1 ms 340 KB OK
11 Correct 1 ms 340 KB OK
12 Correct 1 ms 340 KB OK
13 Correct 1 ms 340 KB OK
14 Correct 1 ms 340 KB OK
15 Correct 0 ms 340 KB OK
16 Correct 1 ms 340 KB OK
17 Correct 1 ms 340 KB OK
18 Correct 2 ms 364 KB OK
19 Correct 3 ms 340 KB OK
20 Correct 0 ms 340 KB OK
21 Correct 49 ms 1464 KB OK
22 Correct 340 ms 1736 KB OK
23 Correct 1622 ms 6320 KB OK
24 Correct 666 ms 2816 KB OK
25 Correct 1 ms 340 KB OK
26 Correct 2 ms 340 KB OK
27 Correct 0 ms 340 KB OK
28 Correct 1 ms 340 KB OK