Submission #716372

#	Time	Username	Problem	Language	Result	Execution time	Memory
716372		FlowerOfSorrow	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	1 ms	212 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#if __cplusplus > 201703L
#include <ranges>
using namespace numbers;
#endif



int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int base, qn, dn, r;
	cin >> base >> qn >> dn >> r;
	vector<int> d(dn);
	copy_n(istream_iterator<int>(cin), dn, d.begin());
	sort(d.begin(), d.end());
	for(auto qi = 0; qi < qn; ++ qi){
		long long obj;
		cin >> obj;
		vector<long long> minval{obj};
		vector dp(1, vector<int>(1, true));
		vector prev(1, vector(1, array{-1, -1}));
		for(auto i = 0; !dp[i].empty() && i <= 100; ++ i){
			minval.push_back((minval.back() - d.back()) / base - 1);
			dp.emplace_back();
			prev.emplace_back();
			for(auto x = 0; x < (int)dp[i].size(); ++ x){
				if(!dp[i][x]){
					continue;
				}
				for(auto y: d){
					if((minval[i] + x - y) % base){
						continue;
					}
					int nx = (minval[i] + x - y) / base - minval[i + 1];
					assert(0 <= nx && nx <= 10000);
					dp[i + 1].resize(max(nx + 1, (int)dp[i + 1].size()));
					prev[i + 1].resize((int)dp[i + 1].size(), {-1, -1});
					dp[i + 1][nx] = true;
					prev[i + 1][nx] = {x, y};
				}
				if(0 <= -minval[i + 1] && -minval[i + 1] < (int)dp[i + 1].size() && dp[i + 1][-minval[i + 1]]){
					for(auto x = -minval[i + 1]; i >= 0; -- i){
						cout << prev[i + 1][x][1] << " ";
						x = prev[i + 1][x][0];
					}
					cout << "\n";
					goto NEXT;
				}
			}
		}
		cout << "IMPOSSIBLE\n";
		NEXT:;
	}
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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