Submission #852199

#	Time	Username	Problem	Language	Result	Execution time	Memory
852199		NaimSS	Weird Numeral System (CCO21_day1problem2)	C++14	8 / 25	2 ms	11356 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;
const int MAX = 120;
bool dp[MAX][SHIFT * 4 + 10];
int vis[MAX][SHIFT*4 + 10];
int go[MAX][SHIFT * 4 + 10];
int T;

vi posi;

int solve(int p,int carry){
    // dbg(p, carry)
    if(abs(carry) >= SHIFT * 4)return 0;
    if(p >= MAX)return 0;
    bool &x = dp[p][carry + SHIFT];

    if(vis[p][carry + SHIFT] == T)return x;
    // cout << p << " " << carry << endl;cout.flush();
    vis[p][carry + SHIFT] = T;
    x = 0;
    if(p >= sz(posi) && carry == 0){
        go[p][carry + SHIFT] = -1;
        return x = 1;
    }
    if(p >= sz(posi)){
        rep(i,0,d){
            int nv = carry + a[i];
            // dbg(p,carry, nv);
            if(nv%k != 0)continue;
            if((nv/k) == 0){
                // dbg("here", p, carry + SHIFT);
                go[p][carry + SHIFT] = i;
                go[p+1][SHIFT] = -1;
                return x = 1;
            }
        }
    }
    // 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))){
            go[p][carry + SHIFT] = i;
            return x = 1;
        }
    }
    return x = 0;
}


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\n";
            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));
            rep(i,0,sz(vals)){
                if(rev)vals[i]*=-1;
                cout << vals[i] <<" \n"[i == sz(vals)-1];
            }
        }else{
            cout << "IMPOSSIBLE\n";
        }

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

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