oj.uz

Submission #1103702

# Submission time Handle Problem Language Result Execution time Memory
1103702 2024-10-21T14:40:55 Z BuzzyBeez Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1835 ms 6216 KB 
#include <bits/stdc++.h>
using namespace std;

map<long long, long long> memo;
vector<long long> arr;

long long k;
// bool attempt(long long R) {
	// if (par.count(R)) return (par[R] != inf);
	// par[R] = inf;
	// for (int x : arr) if (abs(R - x) % K == 0) 
		// if (R == x || attempt((R - x) / K)) {par[R] = x; return 1;}
	// return 0;
// }

bool solve(long long a){
    if(memo.count(a))return memo[a]!=LLONG_MAX;
    memo[a]=LLONG_MAX;
    for(auto x:arr){
        if((a-x)%k==0){
            if(a-x==0||solve((a-x)/k)){
                memo[a]=x;
                return true;
            }
        }
    }
    return false;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// int d, q, m; cin >> k >> q >> d >> m;
	// arr.resize(d);
	// for (int i = 0; i < d; ++i) cin >> arr[i];
	// long long a;
	int q,d,m;
    cin>>k>>q>>d>>m;
    arr.resize(d);
    for(int i=0;i<d;i++)cin>>arr[i];
    long long a;
	while (q--) {
		cin >> a; bool pass = solve(a);
		if (!pass) cout << "IMPOSSIBLE\n";
		else {
			vector<long long> fin; long long cur = a;
            while(1){
                fin.push_back(memo[cur]);
                cur=(cur-memo[cur])/k;
                if(cur==0)break;
            }
            reverse(fin.begin(),fin.end());
			for (int i = 0; i + 1 < fin.size(); ++i) cout << fin[i] << ' ';
			cout << fin.back();
			cout << '\n';
			// vector<long long> ans; long long x;
			// while (1) {
				// x = memo[a]; ans.push_back(x);
				// a = (a - x) / K;
				// if (a == 0) break;
			// }
			// reverse(ans.begin(), ans.end());
			// for (int i : ans) cout << i << ' ';
			// cout << '\n';
		}
	}
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK
2 Correct 1 ms 336 KB OK
3 Correct 1 ms 336 KB OK
4 Correct 1 ms 336 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 336 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK
9 Correct 1 ms 336 KB OK
10 Correct 1 ms 504 KB OK
11 Correct 1 ms 336 KB OK
12 Correct 1 ms 512 KB OK
13 Correct 1 ms 336 KB OK
14 Correct 1 ms 336 KB OK
15 Correct 1 ms 336 KB OK
16 Correct 1 ms 336 KB OK
17 Correct 1 ms 336 KB OK
18 Correct 1 ms 336 KB OK
19 Correct 2 ms 336 KB OK
20 Correct 1 ms 336 KB OK
21 Correct 59 ms 1684 KB OK
22 Correct 380 ms 1588 KB OK
23 Correct 1835 ms 6216 KB OK
24 Correct 734 ms 2888 KB OK
25 Correct 1 ms 336 KB OK
26 Correct 1 ms 336 KB OK
27 Correct 1 ms 336 KB OK
28 Correct 1 ms 504 KB OK