Submission #256215

#	Time	Username	Problem	Language	Result	Execution time	Memory
256215		amoo_safar	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	69 ms	4208 KiB

brunhilda

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int m, Q;

int p[N], ans[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(ans, -1, sizeof ans);
	cin >> m >> Q;
	for(int i = 0; i < m; i++) cin >> p[i];
	vector< pair<int, int> > V;
	int v;
	for(int i = 0; i < Q; i++){
		cin >> v;
		V.pb({v, i});
	}
	sort(all(V));
	int po = 0;

	int R = 0, R2, cnt = 0;
	while(R <= 10000000){
		R2 = R;
		for(int i = 0; i < m; i++)
			R2 = max(R2, R - (R % p[i]) + p[i] - 1);
		cnt ++;
		while((po < (int) V.size()) && (V[po].F <= R2)){
			ans[V[po ++].S] = cnt;
		}
		if(R2 == R) break;
		R = R2;
	}

	for(int i = 0; i < Q; i++){
		if(ans[i] == -1) cout << "oo\n";
		else cout << ans[i] << '\n';
	}
	return 0;
}

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