oj.uz

Submission #412379

# Submission time Handle Problem Language Result Execution time Memory
412379 2021-05-26T18:35:23 Z thomas_li Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1926 ms 131676 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;
					if(par[u].first != -2e18) cout << " ";
					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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 131524 KB OK
2 Correct 129 ms 131568 KB OK
3 Correct 132 ms 131604 KB OK
4 Correct 127 ms 131516 KB OK
5 Correct 129 ms 131512 KB OK
6 Correct 126 ms 131536 KB OK
7 Correct 129 ms 131524 KB OK
8 Correct 140 ms 131632 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 131524 KB OK
2 Correct 129 ms 131568 KB OK
3 Correct 132 ms 131604 KB OK
4 Correct 127 ms 131516 KB OK
5 Correct 129 ms 131512 KB OK
6 Correct 126 ms 131536 KB OK
7 Correct 129 ms 131524 KB OK
8 Correct 140 ms 131632 KB OK
9 Correct 140 ms 131636 KB OK
10 Correct 133 ms 131640 KB OK
11 Correct 130 ms 131524 KB OK
12 Correct 127 ms 131560 KB OK
13 Correct 268 ms 131644 KB OK
14 Correct 156 ms 131628 KB OK
15 Correct 144 ms 131524 KB OK
16 Correct 126 ms 131588 KB OK
17 Correct 136 ms 131524 KB OK
18 Correct 1225 ms 131648 KB OK
19 Correct 1926 ms 131652 KB OK
20 Correct 129 ms 131568 KB OK
21 Correct 166 ms 131576 KB OK
22 Correct 452 ms 131596 KB OK
23 Correct 839 ms 131536 KB OK
24 Correct 456 ms 131524 KB OK
25 Correct 735 ms 131640 KB OK
26 Correct 846 ms 131676 KB OK
27 Correct 110 ms 131540 KB OK
28 Correct 86 ms 131524 KB OK