oj.uz

답안 #412378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412378 2021-05-26T18:34:24 Z thomas_li Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 134 ms 131620 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
int main(){
	cin.tie(0)->sync_with_stdio(0); 
	int k,t,d,m; cin >> k >> t >> d >> m;
	vector<int> a(d); for(int& v : a) cin >> v;
	gp_hash_table<ll,pair<ll,int>> par({},{},{},{},{1<<22});
	while(t--){
		ll x; cin >> x;
		par.clear(); par[x] = {-2e18,-1};
		queue<ll> q; q.push(x);
		bool good = 0; int cnt = 0;
		while(q.size() && !good && cnt < 1.5e5){
			ll u = q.front(); q.pop();
			//cout << u << "\n";
			for(int w : a){
				if((u-w)%k != 0) continue;
				ll v = (u-w)/k;
				//cout << u << "->" << v << "\n";
				if(v == 0){
					cout << w << " ";
					while(1){
						if(par[u].first == -2e18) break;
						cout << par[u].second;
						if(par[par[u].first].first != -2e18) cout << " ";
						u = par[u].first;
					}
					cout << "\n";
					good = 1;
					break;
				}
				if(par.find(v) == par.end()){
					q.push(v); par[v] = {u,w};
					//cout << v << " " << w << "\n";
				}
			}
		}
		if(!good) cout << "IMPOSSIBLE\n";
	}
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 131588 KB OK
2 Correct 130 ms 131528 KB OK
3 Correct 126 ms 131620 KB OK
4 Incorrect 127 ms 131524 KB For n=0, representation is not correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 131588 KB OK
2 Correct 130 ms 131528 KB OK
3 Correct 126 ms 131620 KB OK
4 Incorrect 127 ms 131524 KB For n=0, representation is not correct
5 Halted 0 ms 0 KB -