oj.uz

Submission #559464

# Submission time Handle Problem Language Result Execution time Memory
559464 2022-05-09T22:54:15 Z Trunkty Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 414 ms 136216 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

#define DEBUG
#ifdef DEBUG
  #define debug(x) cout << #x << ": " << x << endl
#else
  #define debug(x)
#endif

int m,q;
vector<int> upd[1000005];
int cnt[1000005];
int curr[1000005];
int ans[1000005],lp=0,maxi=2e9;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> m >> q;
	for(int i=1;i<=m;i++){
		int a;
		cin >> a;
		for(int j=a;j<=1e6;j+=a){
			upd[j].push_back(a);
		}
		cnt[0]++;
	}
	for(int i=1;i<=1e6;i++){
		for(int j:upd[i]){
			cnt[curr[j]]--;
			curr[j] = i;
			cnt[curr[j]]++;
		}
		while(lp!=i and !cnt[lp]){
			lp++;
		}
		if(lp==i){
			maxi = i;
			break;
		}
		ans[i] = ans[lp]+1;
	}
	for(int i=1;i<=q;i++){
		int a;
		cin >> a;
		if(a<maxi){
			cout << ans[a] << "\n";
		}
		else{
			cout << "oo" << "\n";
		}
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29140 KB Output is correct
2 Correct 96 ms 54276 KB Output is correct
3 Correct 59 ms 45420 KB Output is correct
4 Correct 33 ms 33996 KB Output is correct
5 Correct 44 ms 39832 KB Output is correct
6 Correct 24 ms 29060 KB Output is correct
7 Correct 57 ms 45412 KB Output is correct
8 Correct 81 ms 54392 KB Output is correct
9 Correct 104 ms 57292 KB Output is correct
10 Correct 140 ms 58200 KB Output is correct
11 Correct 110 ms 53696 KB Output is correct
12 Correct 30 ms 33252 KB Output is correct
13 Correct 259 ms 61112 KB Output is correct
14 Correct 278 ms 61156 KB Output is correct
15 Correct 97 ms 53760 KB Output is correct
16 Correct 98 ms 54352 KB Output is correct
17 Correct 58 ms 39832 KB Output is correct
18 Correct 39 ms 34052 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 81692 KB Execution killed with signal 11
2 Incorrect 76 ms 42620 KB Output isn't correct
3 Incorrect 395 ms 67540 KB Output isn't correct
4 Runtime error 114 ms 91124 KB Execution killed with signal 11
5 Incorrect 219 ms 61956 KB Output isn't correct
6 Incorrect 82 ms 50764 KB Output isn't correct
7 Runtime error 80 ms 81740 KB Execution killed with signal 11
8 Incorrect 87 ms 43468 KB Output isn't correct
9 Incorrect 272 ms 64316 KB Output isn't correct
10 Incorrect 387 ms 67508 KB Output isn't correct
11 Runtime error 391 ms 129864 KB Execution killed with signal 11
12 Incorrect 164 ms 55860 KB Output isn't correct
13 Runtime error 75 ms 83488 KB Execution killed with signal 11
14 Runtime error 118 ms 91212 KB Execution killed with signal 11
15 Incorrect 311 ms 64516 KB Output isn't correct
16 Incorrect 64 ms 42628 KB Output isn't correct
17 Runtime error 311 ms 123012 KB Execution killed with signal 11
18 Incorrect 292 ms 64716 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 311 ms 133580 KB Execution killed with signal 11
2 Runtime error 398 ms 132800 KB Execution killed with signal 11
3 Incorrect 398 ms 66212 KB Output isn't correct
4 Runtime error 202 ms 115376 KB Execution killed with signal 11
5 Runtime error 96 ms 85484 KB Execution killed with signal 11
6 Runtime error 298 ms 121916 KB Execution killed with signal 11
7 Incorrect 208 ms 59556 KB Output isn't correct
8 Runtime error 309 ms 133492 KB Execution killed with signal 11
9 Runtime error 321 ms 133568 KB Execution killed with signal 11
10 Runtime error 212 ms 111096 KB Execution killed with signal 11
11 Runtime error 165 ms 103884 KB Execution killed with signal 11
12 Runtime error 278 ms 121012 KB Execution killed with signal 11
13 Incorrect 368 ms 64228 KB Output isn't correct
14 Incorrect 164 ms 60056 KB Output isn't correct
15 Runtime error 297 ms 123724 KB Execution killed with signal 11
16 Runtime error 332 ms 124704 KB Execution killed with signal 11
17 Runtime error 279 ms 126432 KB Execution killed with signal 11
18 Runtime error 394 ms 132768 KB Execution killed with signal 11
19 Runtime error 90 ms 96264 KB Execution killed with signal 11
20 Incorrect 388 ms 66252 KB Output isn't correct
21 Runtime error 212 ms 121956 KB Execution killed with signal 11
22 Runtime error 378 ms 136216 KB Execution killed with signal 11
23 Runtime error 102 ms 89292 KB Execution killed with signal 11
24 Runtime error 73 ms 76516 KB Execution killed with signal 11
25 Runtime error 219 ms 113392 KB Execution killed with signal 11
26 Runtime error 203 ms 115444 KB Execution killed with signal 11
27 Incorrect 414 ms 68980 KB Output isn't correct
28 Runtime error 87 ms 87292 KB Execution killed with signal 11
29 Runtime error 300 ms 132408 KB Execution killed with signal 11
30 Runtime error 260 ms 130464 KB Execution killed with signal 11
31 Runtime error 103 ms 90984 KB Execution killed with signal 11
32 Runtime error 126 ms 95724 KB Execution killed with signal 11
33 Runtime error 61 ms 72296 KB Execution killed with signal 11
34 Incorrect 219 ms 59640 KB Output isn't correct
35 Runtime error 99 ms 88652 KB Execution killed with signal 11
36 Runtime error 363 ms 135764 KB Execution killed with signal 11
37 Runtime error 97 ms 85496 KB Execution killed with signal 11
38 Runtime error 292 ms 121992 KB Execution killed with signal 11
39 Runtime error 89 ms 80220 KB Execution killed with signal 11
40 Runtime error 255 ms 119844 KB Execution killed with signal 11
41 Incorrect 199 ms 61832 KB Output isn't correct
42 Runtime error 322 ms 124196 KB Execution killed with signal 11