Submission #411674

#	Time	Username	Problem	Language	Result	Execution time	Memory
411674		ChrisT	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	91 ms	23820 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 17 / 17