oj.uz

답안 #852361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852361 2023-09-21T16:26:35 Z NaimSS Weird Numeral System (CCO21_day1problem2) C++14
8 / 25
 2 ms 9304 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 * 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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB OK
2 Correct 2 ms 8792 KB OK
3 Correct 2 ms 8796 KB OK
4 Correct 2 ms 8796 KB OK
5 Correct 2 ms 8792 KB OK
6 Correct 2 ms 8796 KB OK
7 Correct 2 ms 9048 KB OK
8 Correct 2 ms 9048 KB OK

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB OK
2 Correct 2 ms 8792 KB OK
3 Correct 2 ms 8796 KB OK
4 Correct 2 ms 8796 KB OK
5 Correct 2 ms 8792 KB OK
6 Correct 2 ms 8796 KB OK
7 Correct 2 ms 9048 KB OK
8 Correct 2 ms 9048 KB OK
9 Correct 2 ms 9048 KB OK
10 Correct 2 ms 9052 KB OK
11 Correct 2 ms 9052 KB OK
12 Correct 2 ms 9048 KB OK
13 Correct 2 ms 9304 KB OK
14 Correct 2 ms 9052 KB OK
15 Correct 2 ms 9048 KB OK
16 Incorrect 2 ms 8796 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -