Submission #1096390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096390		slah007	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	2098 ms	1640 KiB

Main

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#include <map>
using namespace std;

const int MAXK = 1e6;
const int MAXM = 2500;
const int MAXD = MAXM<<1|1;
const int NAN = 998244353;

int K, Q, D, M;
set<int> digits;

map<long long, int> dp;
int go(long long n){
    if(dp.count(n)) return dp[n];
    if(digits.count(n)){
        return dp[n] = n;
    }
    dp[n] = NAN;
    for(auto x : digits){
        if((n-x)%K == 0){
            long long t = (n-x)/K;
            if(go(t) != NAN){
                return dp[n] = x;
            }
        }
    }
    return NAN;
}

int main(){
    scanf("%d %d %d %d", &K, &Q, &D, &M);
    for(int i=0;i<D;i++){
        int x;
        scanf("%d", &x);
        digits.insert(x);
    }
    while(Q--){
        long long n;
        scanf("%lld", &n);
        dp.clear();
        if(go(n) != NAN){
            vector<int> v;
            do{
                v.push_back(dp[n]);
                n = (n - dp[n]) / K;
            }while(n);
            reverse(v.begin(), v.end());
            for(int i=0;i<(int)v.size();i++){
                printf("%d%c", v[i], " \n"[i+1==(int)v.size()]);
            }
        }
        else{
            puts("IMPOSSIBLE");
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d %d %d", &K, &Q, &D, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
Main.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld", &n);
      |         ~~~~~^~~~~~~~~~~~

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