oj.uz

Submission #416726

# Submission time Handle Problem Language Result Execution time Memory
416726 2021-06-02T20:42:12 Z inksamurai Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1236 ms 1104 KB 
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip> 
#include <stdio.h>
//eolibraries
#define lnf 3999999999999999999
#define inf 999999999
#define PI 3.14159265359
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define all(c) (c).begin(),(c).end()
#define sz(c) (ll)(c).size()
#define mkp(a,b) make_pair(a,b)
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define rsz(a,n) a.resize(n)
#define pii pair <ll,ll>
#define rep(i,n) for(ll i = 0 ; i < n ; i++) 
#define drep(i,n) for(ll i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(ll i = x ; i < n ; i++)
#define vi vector <ll> 
#define vec(s) vector<s>
#define rsz(a,n) a.resize(n)
#define rszv(a,n,v) a.resize(n,v)
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//eodefine
 
const ll max_n = 103002;
 
using namespace std;
 
ll k,n,q,m;
vi a;
 
 
unordered_map <ll,ll> memo;
vi tmp;
 
ll slv(ll x){
 
	if(memo.find(x)!=memo.end()) return memo[x];
	
	memo[x]=0;

	rep(i,n) {
		if(x-a[i] == 0) {
			tmp.pb(a[i]);
			// cout << x << "\n";
			return memo[x] = 1;
		}
		
		if((x-a[i])%k!=0) continue;
		
		ll nex=(x-a[i])/k;
 		
		if(nex==x)continue;
	
		slv(nex);
 
		if(memo[nex]==1) {tmp.pb(a[i]); return memo[x]=1;	}
	
	}
 
	return memo[x]=0;
}
 
int main(){
fcin;
	cin>>k>>q>>n>>m;
	rep(i,n){ll x;cin>>x;a.pb(x);}
 
	rep(_,q) {
		ll val;
		cin>>val;
		// cout << val << "\n";
		tmp.clear();
		memo.clear();
		if(slv(val)==0)  { 
			cout << "IMPOSSIBLE"; 
		} else {
			rep(i,sz(tmp)) {
				cout<<tmp[i];
				if(i<sz(tmp)-1)cout<<" ";
			}
		}
		cout<<"\n";
	}
 
/*
*/
 
    return 0;   
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK
2 Correct 0 ms 204 KB OK
3 Correct 1 ms 204 KB OK
4 Correct 1 ms 204 KB OK
5 Correct 0 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 1 ms 204 KB OK
8 Correct 1 ms 204 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK
2 Correct 0 ms 204 KB OK
3 Correct 1 ms 204 KB OK
4 Correct 1 ms 204 KB OK
5 Correct 0 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 1 ms 204 KB OK
8 Correct 1 ms 204 KB OK
9 Correct 1 ms 332 KB OK
10 Correct 1 ms 204 KB OK
11 Correct 1 ms 204 KB OK
12 Correct 1 ms 204 KB OK
13 Correct 1 ms 332 KB OK
14 Correct 1 ms 332 KB OK
15 Correct 1 ms 332 KB OK
16 Correct 0 ms 204 KB OK
17 Correct 1 ms 204 KB OK
18 Correct 1 ms 332 KB OK
19 Correct 1 ms 332 KB OK
20 Correct 0 ms 204 KB OK
21 Correct 37 ms 1044 KB OK
22 Correct 253 ms 1104 KB OK
23 Correct 1236 ms 1068 KB OK
24 Correct 500 ms 1092 KB OK
25 Correct 1 ms 332 KB OK
26 Correct 1 ms 332 KB OK
27 Correct 1 ms 204 KB OK
28 Correct 1 ms 204 KB OK