oj.uz

Submission #633868

# Submission time Handle Problem Language Result Execution time Memory
633868 2022-08-23T10:24:50 Z gs14004 Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 2500 ms 23824 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;
	}
	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:26:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |  if(sz(a[modv]) == 0) return dp[N] =false;
Main.cpp:30:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   30 |    return dp[N] = true;
Main.cpp:33:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |  return dp[N] = false;

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB OK
2 Correct 1 ms 340 KB OK
3 Correct 1 ms 340 KB OK
4 Correct 1 ms 340 KB OK
5 Correct 1 ms 340 KB OK
6 Correct 3 ms 340 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 1 ms 340 KB OK
17 Correct 13 ms 23824 KB OK
18 Correct 12 ms 472 KB OK
19 Correct 16 ms 484 KB OK
20 Correct 0 ms 340 KB OK
21 Execution timed out 2561 ms 436 KB Time limit exceeded
22 Halted 0 ms 0 KB -