#include<bits/stdc++.h>
#define int long long
using namespace std;
vector <int> v;
int k, q, d, m;
bool auxx = false;
int fastexpo(int a, int b){
if(b == 0) return 1;
if(b % 2 == 0){
return fastexpo(a*a, b/2);
}
return a*fastexpo(a*a, (b-1)/2);
}
int find(int val, int bit){
int t = fastexpo(k, bit);
// cout << "aa\n";
// cout << val << ' ' << bit << '\n';
// cout << t << '\n';
val = (val % (t*k))/t;
// cout << val << "\n \n";
return val;
}
void bfs(int x){
queue < tuple<int, int, vector <int>> > q;
q.push({x, 0, {}});
while(!q.empty()){
auto [val, bit, vec] = q.front();
q.pop();
if(bit >= 2000) continue;
int t = find(val, bit);
// cout << val << ' ' << bit << ' '<< '\n';
for(int i = 0;i < v.size();i++){
if(v[i] == t){
if(val - t*fastexpo(k, bit) == 0){
int con = (auxx ? -1 : 1);
cout << v[i]*con << ' ';
reverse(vec.begin(), vec.end());
for(auto x : vec){
cout << x*con << ' ';
}
cout << '\n';
return;
}
vector <int> aux = vec;
aux.push_back(v[i]);
q.push({val-t*fastexpo(k, bit), bit+1, aux});
// cout << t << '\n';
}
else if(-v[i] + t == k){
if(val + t*fastexpo(k, bit) == 0){
int con = (auxx ? -1 : 1);
cout << v[i]*con << ' ';
reverse(vec.begin(), vec.end());
for(auto x : vec){
cout << x*con << ' ';
}
cout << '\n';
return;
}
vector <int> aux = vec;
aux.push_back(v[i]);
q.push({val-v[i]*fastexpo(k, bit), bit+1, aux});
}
}
}
cout << "IMPOSSIBLE\n";
return;
}
int32_t main(){
cin >> k >> q >> d >> m;
for(int i = 0;i < d;i++){
int x;
cin >> x;
v.push_back(x);
}
for(int i = 0;i < q;i++){
int x;
cin >> x;
if(x < 0){
for(int i = 0;i < d;i++){
v[i] *= -1;
}
x *= -1;
auxx = true;
}
bfs(x);
if(auxx){
for(int i = 0;i < d;i++){
v[i] *= -1;
}
}
auxx = false;
}
return 0;
}
Compilation message
Main.cpp: In function 'void bfs(long long int)':
Main.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | auto [val, bit, vec] = q.front();
| ^
Main.cpp:47:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0;i < v.size();i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
