oj.uz

Submission #633869

# Submission time Handle Problem Language Result Execution time Memory
633869 2022-08-23T10:26:41 Z gs14004 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 2048 ms 23892 KB 
#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 = 6005;

int k, n, m;
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) <= m){
		if(dist[N + MAXT] <= 1e7) return dp[N] = true;
		return dp[N] = false;
	}
	if(dp.count(N)) return dp[N];
	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;
}

vector<int> w;
void trace(lint N){
	vector<int> v;
	while(N){
		if(abs(N) > m){
			v.push_back(path[N]);
			N -= v.back();
			N /= k;
		}
		else{
			v.push_back(par[N + MAXT]);
			N -= v.back();
			N /= k;
		}
	}
	reverse(all(v));
	w = v;
}


int main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q;
	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(v[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;
					if(x == 0) w.push_back(0);
					else{
						trace(-x / k);
						w.push_back(x);
					}
					for(int i = 0; i < sz(w); i++){
						cout << w[i];
						if(i + 1 < sz(w)) cout << " ";
						else cout <<"\n";
					}
					w.clear();
					break;
				}
			}
			if(!ok) cout << "IMPOSSIBLE\n";
			continue;
		}
		if(dfs(N)){
			trace(N);
			for(int i = 0; i < sz(w); i++){
				cout << w[i];
				if(i + 1 < sz(w)) cout << " ";
				else cout <<"\n";
			}
			w.clear();
		}
		else cout << "IMPOSSIBLE\n";
	}
}

Compilation message

Main.cpp: In function 'bool dfs(lint)':
Main.cpp:22:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |   if(dist[N + MAXT] <= 1e7) return dp[N] = true;
Main.cpp:23:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |   return dp[N] = false;
Main.cpp:27:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |  if(sz(a[modv]) == 0) return dp[N] =false;
Main.cpp:31:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   31 |    return dp[N] = true;
Main.cpp:34:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |  return dp[N] = false;

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB OK
2 Correct 1 ms 340 KB OK
3 Correct 0 ms 340 KB OK
4 Correct 1 ms 340 KB OK
5 Correct 0 ms 340 KB OK
6 Correct 3 ms 468 KB OK
7 Correct 1 ms 340 KB OK
8 Correct 1 ms 340 KB OK
9 Correct 1 ms 340 KB OK
10 Correct 1 ms 340 KB OK
11 Correct 1 ms 340 KB OK
12 Correct 1 ms 340 KB OK
13 Correct 2 ms 468 KB OK
14 Correct 1 ms 468 KB OK
15 Correct 1 ms 468 KB OK
16 Correct 0 ms 340 KB OK
17 Correct 13 ms 23892 KB OK
18 Correct 9 ms 452 KB OK
19 Correct 17 ms 488 KB OK
20 Correct 0 ms 340 KB OK
21 Correct 63 ms 1568 KB OK
22 Correct 434 ms 1656 KB OK
23 Correct 2048 ms 6476 KB OK
24 Correct 828 ms 2864 KB OK
25 Correct 9 ms 456 KB OK
26 Correct 10 ms 448 KB OK
27 Correct 1 ms 468 KB OK
28 Correct 1 ms 328 KB OK