oj.uz

Submission #576304

# Submission time Handle Problem Language Result Execution time Memory
576304 2022-06-13T01:59:09 Z eecs Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 0 ms 212 KB 
// 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Representation cannot be empty
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Representation cannot be empty
2 Halted 0 ms 0 KB -