Submission #412379

#	Time	Username	Problem	Language	Result	Execution time	Memory
412379		thomas_li	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	1926 ms	131676 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
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;
	gp_hash_table<ll,pair<ll,int>> par({},{},{},{},{1<<22});
	while(t--){
		ll x; cin >> x;
		par.clear(); par[x] = {-2e18,-1};
		queue<ll> q; q.push(x);
		bool good = 0; int cnt = 0;
		while(q.size() && !good && cnt < 1.5e5){
			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;
					if(par[u].first != -2e18) cout << " ";
					while(1){
						if(par[u].first == -2e18) break;
						cout << par[u].second;
						if(par[par[u].first].first != -2e18) cout << " ";
						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: 8 / 8
• Subtask 2: 17 / 17