Submission #576304

#	Time	Username	Problem	Language	Result	Execution time	Memory
576304		eecs	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	0 ms	212 KiB

Main

// https://dmoj.ca/src/3641806
#include <bits/stdc++.h>
using namespace std;
const int S = 5005;
typedef long long ll;
int k, q, d, m;
int a[5010], b[85];
bitset < 10010 > dp[85];
inline void rmain() {
    int qwq = (m + k) / (k - 1);
    ll n;
    scanf("%lld", &n);
    ll tmp = n;
    const int l = 80;
    for (int i = 1; i <= l; i++) b[i] = tmp % k, tmp /= k;
    dp[0][0 + S] = 1;
    for (int i = 1; i <= l; i++) {
        dp[i].reset();
        bitset < 10010 > cur;
        for (int j = 1; j <= d; j++) cur |= (a[j] >= 0 ? dp[i - 1] << a[j] : dp[i - 1] >> -a[j]);
        for (int j = -qwq; j <= qwq; j++) {
            dp[i][j + S] = abs(j * k + b[i]) <= qwq + m ? cur[j * k + b[i] + S] : 0;
        }
    }
    tmp = n;
    for (int i = 1; i <= l; i++) {
        tmp /= k;
        if (abs(tmp) <= qwq && dp[i][tmp + S]) {
            for (int cur = i, rest = tmp; cur; cur--) {
                rest = rest * k + b[cur];
                for (int j = 1; j <= d; j++) {
                    int to = rest - a[j];
                    if (abs(to) <= qwq && dp[cur - 1][to + S]) {
                        rest = to;
                        printf("%d%c", a[j], " \n"[cur == 1]);
                        break;
                    }
                }
            }
            return;
        }
    }
    puts("IMPOSSIBLE");
}
int main() {
    scanf("%d%d%d%d", &k, &q, &d, &m);
    for (int i = 1; i <= d; i++) scanf("%d", a + i);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d%d%d", &k, &q, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:47:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     for (int i = 1; i <= d; i++) scanf("%d", a + i);
      |                                  ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17