Submission #230226

#	Time	Username	Problem	Language	Result	Execution time	Memory
230226		kshitij_sodani	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	302 ms	262148 KiB

brunhilda

#include <iostream>	
#include <bits/stdc++.h>	
using namespace std;	
typedef int64_t llo;	
#define mp make_pair	
#define pb push_back	
#define a first	
#define b second	
int ma[100001];

int dp[10000001];
vector<int> fac[10000001];
int main(){	
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	int n,s;
	cin>>n>>s;
	int aa;
	dp[1]=1;
	dp[0]=0;
	priority_queue<pair<int,int>> ac;
	int it[n];
	for(int i=0;i<n;i++){
		cin>>it[i];
		ac.push({1,i});
		ma[i]=1;
	}
	for(int i=0;i<n;i++){
		for(int j=it[i];j<10000001;j+=it[i]){
			fac[j].pb(i);

		}
	}
	int co=1;
	for(int j=2;j<10000001;j++){
		for(auto k:fac[j]){
			ma[k]=-co;
			ac.push({-co,k});
		}
		int prev=j;
		while(ac.size()){
			pair<int,int> x=ac.top();
			if(ma[x.b]!=x.a){
				ac.pop();
				continue;
			}
			prev=j-(x.a+co);
			break;
		}
		if(prev==j){
			dp[j]=-1;
		}
		else if(dp[prev]!=-1){
			dp[j]=dp[prev]+1;
		}
		else{
			dp[j]=-1;
		}

		co+=1;
	}


	while(s--){
		cin>>aa;
		if(dp[aa]==-1){
			cout<<"oo"<<endl;
		}
		else{
			cout<<dp[aa]<<endl;
		}
	}




	

	return 0;	
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60