Submission #852178

#	Time	Username	Problem	Language	Result	Execution time	Memory
852178		NaimSS	Weird Numeral System (CCO21_day1problem2)	C++14	0 / 25	1 ms	344 KiB

Main

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(v) begin(v),end(v)
#define endl '\n'
#define sz(v) ((int)v.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;


void dbg_out(){ cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "): ", dbg_out(__VA_ARGS__), cerr << endl;
#else
#define dbg(...) 42
#endif

mt19937 rng(422);
int k,d;

int a[2505];
const int SHIFT = 2500 * 2;
bool dp[SHIFT * 4 + 10][80];
int vis[SHIFT*4 + 10][80];
int go[SHIFT * 4 + 10][80];
int T;

vi posi;

int solve(int p,int carry){
    if(abs(carry) >= SHIFT * 4)return 0;
    if(p >= 80)return 0;
    bool &x = dp[p][carry + SHIFT];
    if(vis[p][carry + SHIFT] == T)return x;
    vis[p][carry + SHIFT] = T;
    if(p >= sz(posi) && carry == 0){
        go[p][carry + SHIFT] = -1;
        x=1;
        return x;
    }
    
    // dbg(p, carry);
    rep(i,0,d){
        int nv = carry + a[i] - (p < sz(posi) ? posi[p] : 0);
        if(nv%k !=0 )continue;
        // dbg(p,carry,nv, a[i], nv/k);
        if(solve(p+1,(nv/k))){
            x = 1;
            go[p][carry + SHIFT] = i;
            break;
        }
    }
    return x;
}


int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int q,m;
    cin >> k >> q >> d >> m;
    rep(i,0,d)cin >> a[i];
    sort(a,a+d);
    while(q--){
        posi.clear();
        ll N;
        cin >> N;
        int rev = 0;
        if( N < 0 ){
            N *= -1;
            rep(i,0,d)a[i] = -a[i];
            rev = 1;
        }
        if(N == 0) {
            int ok =0;
            rep(i,0,d){
                if(a[i] == 0){
                    ok = 1;
                }
            }
            if(ok)cout << 0 << endl;
            else cout << "IMPOSSIBLE\n";
            continue;
        }

        while( N > 0 )posi.pb( N % k), N/= k;
        T++;


        if(solve(0,0)){
            int p = 0,carry = 0;
            vi vals;
            while(1){
                
                int i = go[p][carry + SHIFT];
                if(i==-1)break;
                carry = (carry + a[i] - ( p < sz(posi)? posi[p] : 0))/k;
                vals.pb(a[i]);
                p++;
            }
            reverse(all(vals));
            for(auto x : vals){
                if(rev)x=-x;
                cout << x << " ";
            }
            cout << endl;
        }else{
            cout << "IMPOSSIBLE\n";
        }

        if(rev){
            rep(i,0,d)a[i] = -a[i];
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int _Z5solveii.part.0(int, int)':
Main.cpp:42:28: warning: array subscript 5000 is above array bounds of 'int [80]' [-Warray-bounds]
   42 |         go[p][carry + SHIFT] = -1;
      |         ~~~~~~~~~~~~~~~~~~~^
Main.cpp:38:34: warning: array subscript 5000 is above array bounds of 'bool [80]' [-Warray-bounds]
   38 |     bool &x = dp[p][carry + SHIFT];
      |               ~~~~~~~~~~~~~~~~~~~^

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