oj.uz

Submission #413352

# Submission time Handle Problem Language Result Execution time Memory
413352 2021-05-28T14:33:45 Z sebinkim Weird Numeral System (CCO21_day1problem2) C++14
8 / 25
 2500 ms 26636 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

map<ll, ll> M;
queue<ll> Q;
vector<ll> A[1010101];
ll k, q, d, m;

void tc(ll n) {
	ll t, u;

	M.clear();
	for (; !Q.empty(); Q.pop());
	if (n) Q.push(n);
	else {
		for (ll &a: A[0]) {
			if (a == 0) {
				cout << "0\n";
				return;
			}
			u = -a / k;
			M[u] = 0; Q.push(u);
		}
	}

	for (; !Q.empty(); ) {
		t = Q.front(); Q.pop();
		if (t == 0) {
			bool f = 0;
			for (; !f || t != n; t = M[t]) {
				if (f) cout << " ";
				f = 1; cout << (M[t] - t * k);
			}
			cout << "\n";
			return;
		}
		for (ll &a: A[(t % k + k) % k]) {
			u = (t - a) / k;
			if (M.find(u) == M.end()) {
				M[u] = t; Q.push(u);
			}
		}
	}
	cout << "IMPOSSIBLE\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll i, t, n;

	cin >> k >> q >> d >> m;

	for (i = 0; i < d; i++) {
		cin >> t; A[(t % k + k) % k].push_back(t);
	}

	for (; q--; ) {
		cin >> n; tc(n);
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB OK
2 Correct 14 ms 24012 KB OK
3 Correct 15 ms 23968 KB OK
4 Correct 14 ms 24008 KB OK
5 Correct 15 ms 24012 KB OK
6 Correct 14 ms 24012 KB OK
7 Correct 14 ms 24012 KB OK
8 Correct 14 ms 23972 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB OK
2 Correct 14 ms 24012 KB OK
3 Correct 15 ms 23968 KB OK
4 Correct 14 ms 24008 KB OK
5 Correct 15 ms 24012 KB OK
6 Correct 14 ms 24012 KB OK
7 Correct 14 ms 24012 KB OK
8 Correct 14 ms 23972 KB OK
9 Correct 43 ms 25632 KB OK
10 Correct 23 ms 24568 KB OK
11 Correct 17 ms 24180 KB OK
12 Correct 19 ms 24268 KB OK
13 Correct 301 ms 26412 KB OK
14 Correct 72 ms 24772 KB OK
15 Correct 32 ms 24352 KB OK
16 Correct 15 ms 23956 KB OK
17 Correct 14 ms 24012 KB OK
18 Execution timed out 2562 ms 26636 KB Time limit exceeded
19 Halted 0 ms 0 KB -