oj.uz

답안 #633853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633853 2022-08-23T10:01:37 Z gs14004 Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 143 ms 7592 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 = 320005;

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;
}

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));
	for(int i = 0; i < sz(v); i++){
		cout << v[i];
		if(i + 1 < sz(v)) cout << " ";
		else cout <<"\n";
	}
}


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) cout << "0\n";
					else cout << x << " ";
					trace(-x / k);
					break;
				}
			}
			if(!ok) cout << "IMPOSSIBLE\n";
			continue;
		}
		if(dfs(N)){
			trace(N);
		}
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7124 KB OK
2 Correct 4 ms 6100 KB OK
3 Correct 6 ms 6100 KB OK
4 Correct 6 ms 6228 KB OK
5 Correct 5 ms 5076 KB OK
6 Correct 143 ms 6468 KB OK
7 Correct 10 ms 6692 KB OK
8 Correct 8 ms 6092 KB OK

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7124 KB OK
2 Correct 4 ms 6100 KB OK
3 Correct 6 ms 6100 KB OK
4 Correct 6 ms 6228 KB OK
5 Correct 5 ms 5076 KB OK
6 Correct 143 ms 6468 KB OK
7 Correct 10 ms 6692 KB OK
8 Correct 8 ms 6092 KB OK
9 Incorrect 21 ms 7592 KB For n=0, representation is not correct
10 Halted 0 ms 0 KB -