Submission #633826

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

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int mod = 1e9 + 7;
const int MAXT = 10005;

int k, n;
vector<vector<int>> a;

int Mod(lint x){
	return (x % k + k) % k;
}

int dist[3 * MAXT], par[3 * MAXT];
map<lint, int> dp, path;

bool dfs(lint N){
	if(abs(N) <= MAXT && dist[N + MAXT] <= 1e7){
		return dp[N] = true;
	}
	lint modv = Mod(N);
	if(sz(a[modv]) == 0) return dp[N] =false;
	for(auto &x : a[modv]){
		if(dfs((N - x) / k)){
			path[N] = x;
			return dp[N] = true;
		}
	}
	return dp[N] = false;
}

void trace(lint N){
	vector<int> v;
	while(abs(N) > MAXT || dist[N + MAXT] > 1e7){
		v.push_back(path[N]);
		N -= v.back();
		N /= k;
	}
	while(N){
		v.push_back(par[N + MAXT]);
		N -= v.back();
		N /= k;
	}
	reverse(all(v));
	for(auto &x : v) cout << x << " ";
}


int main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q, m;
	cin >> k >> q >> n >> m;
	a.resize(k);
	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
		a[Mod(v[i])].push_back(i);
	}
	memset(dist, 0x3f, sizeof(dist));
	queue<int> que;
	auto enq = [&](lint x, int d, int p){
		if(abs(x) > MAXT) return;
		if(dist[x + MAXT] > d){
			dist[x + MAXT] = d;
			par[x + MAXT] = p;
			que.push(x);
		}
	};
	enq(0, 0, -1);
	while(sz(que)){
		int x = que.front(); que.pop();
		for(int i = 0; i < n; i++){
			enq(1ll * x * k + v[i], dist[x + MAXT] + 1, v[i]);
		}
	}
	while(q--){
		lint N; cin >> N;
		if(N == 0){
			bool ok = 0;
			for(auto &x : a[0]){
				if(dfs(-x / k)){
					ok = 1;
					cout << " " << x << "\n";
					trace(-x / k);
					break;
				}
			}
			if(!ok) cout << "IMPOSSIBLE\n";
			continue;
		}
		if(dfs(N)){
			trace(N);
			cout << "\n";
		}
		else cout << "IMPOSSIBLE\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'bool dfs(lint)':
Main.cpp:22:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |   return dp[N] = true;
Main.cpp:25:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |  if(sz(a[modv]) == 0) return dp[N] =false;
Main.cpp:29:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   29 |    return dp[N] = true;
Main.cpp:32:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |  return dp[N] = false;

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