답안 #722274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722274	2023-04-11T16:42:31 Z	PoPularPlusPlus	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	41.5873 / 100	91 ms	41512 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

const int N = 10000002;
int ans[N];

void solve(){
	int n , qu;
	cin >> n >> qu;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	queue<pair<int,int>> q;
	for(int i = 0; i < n; i++){
		q.push(mp(0,i));
	}
	for(int i = 1; i <= N-2; i++){
		while(q.size()){
			if(q.front().vf + arr[q.front().vs] <= i){
				int mul = i/arr[q.front().vs];
				q.push(mp(mul*arr[q.front().vs] , q.front().vs));
				q.pop();
			}
			else break;
		}
		ans[i] = 1e9;
		ans[i] = ans[q.front().vf] + 1;
	}
	while(qu--){
		int x;
		cin >> x;
		if(ans[x] >= 1e9)cout << "oo\n";
		else cout << ans[x] << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
   // int t;cin>>t;
   // while(t--){
		solve();
	//}
	return 0;
}

Subtask #1

4.44444444444 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	60 ms	39372 KB	Output isn't correct
2	Incorrect	69 ms	39332 KB	Output isn't correct
3	Incorrect	77 ms	39380 KB	Output isn't correct
4	Incorrect	51 ms	39344 KB	Output isn't correct
5	Correct	54 ms	39372 KB	Output is correct
6	Incorrect	59 ms	39424 KB	Output isn't correct
7	Incorrect	59 ms	39316 KB	Output isn't correct
8	Incorrect	81 ms	39340 KB	Output isn't correct
9	Incorrect	64 ms	39380 KB	Output isn't correct
10	Incorrect	56 ms	39452 KB	Output isn't correct
11	Incorrect	71 ms	39340 KB	Output isn't correct
12	Correct	53 ms	39384 KB	Output is correct
13	Correct	64 ms	39372 KB	Output is correct
14	Correct	54 ms	39372 KB	Output is correct
15	Incorrect	48 ms	39376 KB	Output isn't correct
16	Incorrect	54 ms	39372 KB	Output isn't correct
17	Incorrect	64 ms	39408 KB	Output isn't correct
18	Incorrect	50 ms	39460 KB	Output isn't correct

Subtask #2

10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	39496 KB	Output is correct
2	Correct	53 ms	40516 KB	Output is correct
3	Incorrect	56 ms	40264 KB	Output isn't correct
4	Incorrect	50 ms	39408 KB	Output isn't correct
5	Correct	61 ms	39956 KB	Output is correct
6	Correct	62 ms	39344 KB	Output is correct
7	Correct	49 ms	39500 KB	Output is correct
8	Incorrect	47 ms	39376 KB	Output isn't correct
9	Correct	57 ms	40312 KB	Output is correct
10	Incorrect	52 ms	40196 KB	Output isn't correct
11	Incorrect	55 ms	39824 KB	Output isn't correct
12	Incorrect	51 ms	39372 KB	Output isn't correct
13	Correct	42 ms	39372 KB	Output is correct
14	Incorrect	46 ms	39588 KB	Output isn't correct
15	Correct	55 ms	39916 KB	Output is correct
16	Correct	58 ms	40516 KB	Output is correct
17	Incorrect	54 ms	39372 KB	Output isn't correct
18	Incorrect	62 ms	40652 KB	Output isn't correct

Subtask #3

27.1428571429 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	40244 KB	Output is correct
2	Correct	61 ms	40196 KB	Output is correct
3	Incorrect	60 ms	40480 KB	Output isn't correct
4	Incorrect	70 ms	40220 KB	Output isn't correct
5	Correct	77 ms	41288 KB	Output is correct
6	Incorrect	74 ms	40312 KB	Output isn't correct
7	Correct	65 ms	40964 KB	Output is correct
8	Correct	64 ms	40252 KB	Output is correct
9	Correct	62 ms	40280 KB	Output is correct
10	Incorrect	67 ms	39524 KB	Output isn't correct
11	Incorrect	65 ms	39560 KB	Output isn't correct
12	Incorrect	56 ms	39724 KB	Output isn't correct
13	Incorrect	57 ms	40572 KB	Output isn't correct
14	Incorrect	71 ms	40352 KB	Output isn't correct
15	Incorrect	63 ms	39632 KB	Output isn't correct
16	Incorrect	77 ms	39496 KB	Output isn't correct
17	Correct	57 ms	39908 KB	Output is correct
18	Correct	62 ms	40164 KB	Output is correct
19	Correct	51 ms	39620 KB	Output is correct
20	Incorrect	60 ms	40424 KB	Output isn't correct
21	Incorrect	64 ms	40396 KB	Output isn't correct
22	Correct	91 ms	41512 KB	Output is correct
23	Correct	73 ms	40576 KB	Output is correct
24	Incorrect	75 ms	40396 KB	Output isn't correct
25	Incorrect	85 ms	40356 KB	Output isn't correct
26	Incorrect	74 ms	40260 KB	Output isn't correct
27	Incorrect	68 ms	41088 KB	Output isn't correct
28	Incorrect	55 ms	40544 KB	Output isn't correct
29	Correct	84 ms	41460 KB	Output is correct
30	Correct	88 ms	41088 KB	Output is correct
31	Correct	84 ms	40256 KB	Output is correct
32	Incorrect	74 ms	40384 KB	Output isn't correct
33	Incorrect	66 ms	40312 KB	Output isn't correct
34	Correct	69 ms	41024 KB	Output is correct
35	Incorrect	56 ms	40424 KB	Output isn't correct
36	Correct	89 ms	41256 KB	Output is correct
37	Correct	78 ms	41292 KB	Output is correct
38	Incorrect	71 ms	40332 KB	Output isn't correct
39	Incorrect	71 ms	40424 KB	Output isn't correct
40	Correct	76 ms	40272 KB	Output is correct
41	Correct	70 ms	40944 KB	Output is correct
42	Incorrect	60 ms	40404 KB	Output isn't correct