Submission #852361

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

int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

 
vi posi;
int TAM;

int solve(int p,int carry){
    // dbg(p, carry)
    if(abs(carry) >= SHIFT * 2)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;
    go[p][carry + SHIFT] = 0;
    x = 0;
    if(p >= TAM && carry == 0){
        go[p][carry + SHIFT] = -1;
        return x = 1;
    }
    if(p >= TAM){
        rep(i,0,d){
            int nv = carry + a[i];
            // dbg(p,carry, nv);
            if((nv%k + k)%k != (posi[p]%k + k)%k)continue;
            if(fdiv(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] ;
        if((nv%k + k)%k != (posi[p]%k + k)%k)continue;
        // dbg(p,carry,nv, a[i], nv/k);
        if(solve(p+1,fdiv(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)posi.pb(0);
        while( N > 0 )posi.pb( N % k), N/= k;
        TAM = sz(posi);
        while(sz(posi) < MAX)posi.pb(0);
        T++;
        memset(dp,0,sizeof(dp)),memset(go,0,sizeof(go));
 
 
        if(solve(0,0)){
            int p = 0,carry = 0;
            vi vals;
            while(1){
                
                int i = go[p][carry + SHIFT];
                if(i==-1)break;
                carry = fdiv(carry + a[i],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