oj.uz

Submission #411674

# Submission time Handle Problem Language Result Execution time Memory
411674 2021-05-25T17:38:42 Z ChrisT Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 91 ms 23820 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
bitset<10005> dp[61];
int f (int x, int y) { //floor(x/y)
	if (x >= 0) return x/y;
	return x/y - (x%y!=0);
}
int main () { //only too slow for k=2
	int k,q,d,m; scanf ("%d %d %d %d",&k,&q,&d,&m);
	vector<int> a(d);
	vector<vector<int>> withMod(k);
	for (int &i : a) scanf ("%d",&i);
	while (q--) {
		long long n; scanf ("%lld",&n);
		bool flag = n < 0;
		if (flag) {
			for (int &i : a) i = -i;
			n = -n;
		}
		vector<long long> want(62);
		{
			long long cur = n;
			for (int i = 1; i <= 61; i++) {want[i] = cur; cur /= k;}
		}
		for (int i = 0; i < k; i++) withMod[i].clear();
		for (int i : a) withMod[(i%k+k)%k].push_back(i);
		dp[0][2500] = 1;
		for (int dig = 1; dig <= 60; dig++) {
			dp[dig].reset();
			bitset<10005> can;
			for (int nxt : a) can |= dp[dig-1] << (nxt+2500);
			for (int i = 0; i < 10005; i++) if (can[i]) {
				if (((i-5000)%k+k)%k == (want[dig]%k+k)%k)
					dp[dig][f(i-5000,k)+2500] = 1;
			}
			if (want[dig+1] <= 7500 && dp[dig].test(want[dig+1]+2500)) { //is-this-fft???.....
				vector<int> ret;
				int cur = want[dig+1];
				for (int go = dig; go > 0; go--) {
					for (int nxt : a) {
						int got = k * cur + (want[go]%k+k)%k;
						if ((dp[go-1] << (nxt+2500)).test(got+5000)) {
							cur = got - nxt;
							ret.push_back(nxt);
							break;
						}
					}
				}
				long long got = 0;
				for (int i = 0; i < (int)ret.size(); i++) got = (got * k + ret[i]);
				assert(got == n);
				for (int i = 0; i < (int)ret.size(); i++) printf ("%d%c",flag ? -ret[i] : ret[i]," \n"[i+1==(int)ret.size()]);
				goto succ;
			}
		}
		printf ("IMPOSSIBLE\n");
		succ:;
		if (flag) {
			for (int &i : a) i = -i;
		}
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:10:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  int k,q,d,m; scanf ("%d %d %d %d",&k,&q,&d,&m);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  for (int &i : a) scanf ("%d",&i);
      |                   ~~~~~~^~~~~~~~~
Main.cpp:15:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   long long n; scanf ("%lld",&n);
      |                ~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB OK
2 Correct 4 ms 332 KB OK
3 Correct 4 ms 368 KB OK
4 Correct 4 ms 332 KB OK
5 Correct 6 ms 332 KB OK
6 Correct 44 ms 372 KB OK
7 Correct 3 ms 332 KB OK
8 Correct 3 ms 368 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB OK
2 Correct 4 ms 332 KB OK
3 Correct 4 ms 368 KB OK
4 Correct 4 ms 332 KB OK
5 Correct 6 ms 332 KB OK
6 Correct 44 ms 372 KB OK
7 Correct 3 ms 332 KB OK
8 Correct 3 ms 368 KB OK
9 Correct 7 ms 332 KB OK
10 Correct 6 ms 368 KB OK
11 Correct 3 ms 204 KB OK
12 Correct 5 ms 204 KB OK
13 Correct 18 ms 332 KB OK
14 Correct 11 ms 340 KB OK
15 Correct 6 ms 328 KB OK
16 Correct 3 ms 332 KB OK
17 Correct 74 ms 23820 KB OK
18 Correct 91 ms 352 KB OK
19 Correct 87 ms 348 KB OK
20 Correct 3 ms 368 KB OK
21 Correct 17 ms 332 KB OK
22 Correct 56 ms 372 KB OK
23 Correct 65 ms 368 KB OK
24 Correct 53 ms 348 KB OK
25 Correct 44 ms 320 KB OK
26 Correct 56 ms 352 KB OK
27 Correct 1 ms 204 KB OK
28 Correct 2 ms 332 KB OK