Submission #633867

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
633867	2022-08-23T10:24:17 Z	gs14004	Weird Numeral System (CCO21_day1problem2)	C++17	8 / 25	2500 ms	23856 KB

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, 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	1 ms	468 KB	OK
2	Correct	1 ms	468 KB	OK
3	Correct	1 ms	468 KB	OK
4	Correct	1 ms	468 KB	OK
5	Correct	1 ms	468 KB	OK
6	Correct	6 ms	560 KB	OK
7	Correct	1 ms	468 KB	OK
8	Correct	1 ms	468 KB	OK

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	OK
2	Correct	1 ms	468 KB	OK
3	Correct	1 ms	468 KB	OK
4	Correct	1 ms	468 KB	OK
5	Correct	1 ms	468 KB	OK
6	Correct	6 ms	560 KB	OK
7	Correct	1 ms	468 KB	OK
8	Correct	1 ms	468 KB	OK
9	Correct	1 ms	468 KB	OK
10	Correct	1 ms	468 KB	OK
11	Correct	1 ms	468 KB	OK
12	Correct	1 ms	468 KB	OK
13	Correct	4 ms	468 KB	OK
14	Correct	2 ms	468 KB	OK
15	Correct	2 ms	468 KB	OK
16	Correct	1 ms	468 KB	OK
17	Correct	15 ms	23856 KB	OK
18	Correct	13 ms	468 KB	OK
19	Correct	26 ms	544 KB	OK
20	Correct	0 ms	468 KB	OK
21	Execution timed out	2580 ms	596 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-