oj.uz

답안 #852201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852201 2023-09-21T12:17:29 Z NaimSS Weird Numeral System (CCO21_day1problem2) C++14
8 / 25
 3 ms 11608 KB 
#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;
        // }
        if(N==0)posi.pb(0);
        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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB OK
2 Correct 1 ms 6744 KB OK
3 Correct 1 ms 6744 KB OK
4 Correct 1 ms 4580 KB OK
5 Correct 1 ms 4440 KB OK
6 Correct 1 ms 4444 KB OK
7 Correct 1 ms 5208 KB OK
8 Correct 1 ms 4952 KB OK

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB OK
2 Correct 1 ms 6744 KB OK
3 Correct 1 ms 6744 KB OK
4 Correct 1 ms 4580 KB OK
5 Correct 1 ms 4440 KB OK
6 Correct 1 ms 4444 KB OK
7 Correct 1 ms 5208 KB OK
8 Correct 1 ms 4952 KB OK
9 Correct 2 ms 11352 KB OK
10 Correct 2 ms 11352 KB OK
11 Correct 2 ms 11352 KB OK
12 Correct 2 ms 11352 KB OK
13 Correct 3 ms 11608 KB OK
14 Correct 2 ms 11352 KB OK
15 Correct 2 ms 11352 KB OK
16 Incorrect 1 ms 2392 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -