oj.uz

Submission #446653

# Submission time Handle Problem Language Result Execution time Memory
446653 2021-07-22T22:42:40 Z RGBB Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 977 ms 1180 KB 
#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXD=5005;
int k,q,d,m,coef[MAXD];
vector<int>outp;
unordered_map<ll,bool>memo;
bool solve(ll v){
    if(memo.find(v)!=memo.end())return memo[v];
    memo[v]=false;
    for(int i=0;i<d;i++){
        if(v==coef[i]){
            outp.push_back(coef[i]);
            return memo[v]=true;
        }
        if((v-coef[i])%k!=0)continue;
        if((v-coef[i])/k!=v&&solve((v-coef[i])/k)){
            outp.push_back(coef[i]);
            return memo[v]=true;
        }
    }
    return memo[v];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>k>>q>>d>>m;
    for(int i=0;i<d;i++)cin>>coef[i];
    for(int i=0;i<q;i++){
        ll inp;
        cin>>inp;
        outp.clear();
        memo.clear();
        if(solve(inp)){
            for(int j=0;j<outp.size()-1;j++)cout<<outp[j]<<" ";
            cout<<outp.back()<<"\n";
        }
        else cout<<"IMPOSSIBLE\n";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for(int j=0;j<outp.size()-1;j++)cout<<outp[j]<<" ";
      |                         ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK
2 Correct 0 ms 204 KB OK
3 Correct 0 ms 204 KB OK
4 Correct 1 ms 204 KB OK
5 Correct 0 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 0 ms 204 KB OK
8 Correct 0 ms 204 KB OK
9 Correct 1 ms 332 KB OK
10 Correct 1 ms 332 KB OK
11 Correct 1 ms 204 KB OK
12 Correct 1 ms 204 KB OK
13 Correct 1 ms 332 KB OK
14 Correct 1 ms 336 KB OK
15 Correct 1 ms 332 KB OK
16 Correct 1 ms 204 KB OK
17 Correct 1 ms 204 KB OK
18 Correct 1 ms 332 KB OK
19 Correct 1 ms 332 KB OK
20 Correct 1 ms 204 KB OK
21 Correct 25 ms 1100 KB OK
22 Correct 201 ms 1080 KB OK
23 Correct 977 ms 1180 KB OK
24 Correct 391 ms 1104 KB OK
25 Correct 1 ms 332 KB OK
26 Correct 1 ms 332 KB OK
27 Correct 0 ms 204 KB OK
28 Correct 0 ms 204 KB OK