Submission #507650

#	Time	Username	Problem	Language	Result	Execution time	Memory
507650		ETK	Weird Numeral System (CCO21_day1problem2)	C++14	0 / 25	49 ms	49556 KiB

Main

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=5005;
int K,q,D,M,a[N],b[N],dp[2505][N],lst[2505][N];
int main(){
    K = read(),q = read(),D = read(),M = read();
    rep(i,1,D){
        a[i] = read();
    }
    while(q--){
        ll x = read();
        bool flg = 0;
        int m = 0;
        while(x != 0){
            b[++m] = x % K,x /= K;
        }
        memset(dp,0,sizeof(dp));
        dp[1][K + b[1]] = 1;
        rep(i,1,m+1)rep(j,0,2*K)if(dp[i][j]){
            rep(k,1,D){
                if((a[k] - j) % K == 0){
                    int d = (a[k] - j) / K + 1;
                    dp[i+1][b[i+1] + K - d] = k;
                    lst[i+1][b[i+1] + K - d] = j;
                    if(i >= m && b[i+1] + K - d == K){
                        int now = K;
                        flg = 1;
                        per(t,i+1,2){
                            printf("%d ",a[dp[t][now]]);
                            now = lst[t][now];
                        }
                        break;
                    }
                }
            }
            if(flg)break;
        }
        if(!flg)puts("IMPOSSIBLE");
        while(m)b[m--] = 0;
    }
    return 0;
}

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