Submission #412272

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

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

int main(){
	cin.tie(0)->sync_with_stdio(0); 
	int k,t,d,m; cin >> k >> t >> d >> m;
	vector<int> a(d); for(int& v : a) cin >> v;
	while(t--){
		ll x; cin >> x;
		unordered_map<ll,pair<ll,int>> par; par[x] = {-2e18,-1};
		queue<ll> q; q.push(x);
		bool good = 0;
		while(q.size() && !good){
			ll u = q.front(); q.pop();
			//cout << u << "\n";
			for(int w : a){
				if((u-w)%k != 0) continue;
				ll v = (u-w)/k;
				//cout << u << "->" << v << "\n";
				if(v == 0){
					cout << w << " ";
					while(1){
						if(par[u].first == -2e18) break;
						cout << par[u].second << " ";
						u = par[u].first;
					}
					cout << "\n";
					good = 1;
					break;
				}
				if(par.find(v) == par.end()){
					q.push(v); par[v] = {u,w};
					//cout << v << " " << w << "\n";
				}
			}
		}
		if(!good) cout << "IMPOSSIBLE\n";
	}
}

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