Submission #854342

#	Time	Username	Problem	Language	Result	Execution time	Memory
854342		Juan	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	0 ms	348 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tii tuple<int,int,int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int maxk = 1e6+5, INF=0x3f3f3f3f, MOD=1e9+7;

map<int,bool> have;

int fast_exp(int a, int xp){
	int rt=1;
	while(xp>0){
		if(xp&1) rt*=a;
		xp/=2;
		a*=a;
	}
	return rt;
}

int32_t main(){
	int k,q,d,m; cin >> k >> q >> d >> m;
	for(int i=0; i<d; i++){
		int x; cin >> x;
		have[x]=true;
	}

	while(q--){
		int goal; cin >> goal;
		if(goal==0){
			if(have[0]) cout << 0 << '\n';
			continue;
		}
		bool sinal=false;
		if(goal<0) sinal=true, goal=-goal;

		vector<int> real;
		for(int b=0; fast_exp(k,b)<=goal; b++){
			real.pb(goal%(fast_exp(k,b+1))/fast_exp(k,b));
		}
		vector<int> ans;
		bool stc=false, ok=true;

		if(!sinal){
			for(int b=0; fast_exp(k,b-1)<=goal; b++){
				if(have[real[b]+stc]) ans.pb(real[b]+stc), stc=false;
				else if(have[real[b]+stc-k])ans.pb(real[b]+stc-k), stc=true;
				else {ok=false; break;}
			}
		}
		else{
			for(int& x : real) x=-x;
			for(int b=0; fast_exp(k,b-1)<=goal; b++){
				if(have[real[b]-stc]) ans.pb(real[b]-stc), stc=false;
				else if(have[real[b]-stc+k])ans.pb(real[b]-stc+k), stc=true;
				else {ok=false; break;}
			}
		}

		if(stc || !ok) cout << "IMPOSSIBLE\n";
		else{
			reverse(all(ans));
			for(int x : ans) cout << x << " ";
			cout << '\n';
		}
	}
}

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