oj.uz

Submission #722275

# Submission time Handle Problem Language Result Execution time Memory
722275 2023-04-11T16:45:20 Z PoPularPlusPlus Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 392 ms 44824 KB 
#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];
	set<pair<int,int>> q;
	for(int i = 0; i < n; i++){
		q.insert(mp(0,i));
	}
	for(int i = 1; i <= N-2; i++){
		while(q.size()){
			pair<int,int> p = *q.begin();
			if(p.vf + arr[p.vs] <= i){
				int mul = i/arr[p.vs];
				q.insert(mp(mul*arr[p.vs] , p.vs));
				q.erase(q.begin());
			}
			else break;
		}
		ans[i] = 1e9;
		ans[i] = ans[(*q.begin()).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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 39348 KB Output is correct
2 Correct 167 ms 39452 KB Output is correct
3 Correct 163 ms 39372 KB Output is correct
4 Correct 66 ms 39436 KB Output is correct
5 Correct 185 ms 39360 KB Output is correct
6 Correct 152 ms 39516 KB Output is correct
7 Correct 169 ms 39368 KB Output is correct
8 Correct 186 ms 39392 KB Output is correct
9 Correct 277 ms 39448 KB Output is correct
10 Correct 220 ms 39372 KB Output is correct
11 Correct 240 ms 39396 KB Output is correct
12 Correct 88 ms 39372 KB Output is correct
13 Correct 239 ms 39440 KB Output is correct
14 Correct 236 ms 39500 KB Output is correct
15 Correct 141 ms 39368 KB Output is correct
16 Correct 155 ms 39388 KB Output is correct
17 Correct 177 ms 39424 KB Output is correct
18 Correct 62 ms 39420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40048 KB Output is correct
2 Correct 97 ms 44052 KB Output is correct
3 Correct 178 ms 42960 KB Output is correct
4 Correct 96 ms 39576 KB Output is correct
5 Correct 162 ms 42020 KB Output is correct
6 Correct 63 ms 39388 KB Output is correct
7 Correct 69 ms 39972 KB Output is correct
8 Correct 106 ms 39444 KB Output is correct
9 Correct 214 ms 43052 KB Output is correct
10 Correct 179 ms 42984 KB Output is correct
11 Correct 243 ms 41440 KB Output is correct
12 Correct 138 ms 39488 KB Output is correct
13 Correct 45 ms 39504 KB Output is correct
14 Correct 100 ms 39536 KB Output is correct
15 Correct 219 ms 41564 KB Output is correct
16 Correct 87 ms 44008 KB Output is correct
17 Correct 183 ms 39476 KB Output is correct
18 Correct 158 ms 44492 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 42000 KB Output is correct
2 Correct 307 ms 42216 KB Output is correct
3 Correct 293 ms 42100 KB Output is correct
4 Correct 121 ms 39756 KB Output is correct
5 Correct 145 ms 44824 KB Output is correct
6 Correct 273 ms 40032 KB Output is correct
7 Correct 189 ms 44608 KB Output is correct
8 Correct 242 ms 42056 KB Output is correct
9 Correct 209 ms 42060 KB Output is correct
10 Correct 181 ms 39760 KB Output is correct
11 Correct 146 ms 39628 KB Output is correct
12 Correct 173 ms 39768 KB Output is correct
13 Correct 224 ms 41148 KB Output is correct
14 Correct 366 ms 40140 KB Output is correct
15 Correct 209 ms 39700 KB Output is correct
16 Correct 270 ms 39848 KB Output is correct
17 Correct 219 ms 41676 KB Output is correct
18 Correct 297 ms 42244 KB Output is correct
19 Correct 54 ms 39628 KB Output is correct
20 Correct 309 ms 42128 KB Output is correct
21 Correct 204 ms 39968 KB Output is correct
22 Correct 311 ms 44608 KB Output is correct
23 Correct 172 ms 41164 KB Output is correct
24 Correct 79 ms 39724 KB Output is correct
25 Correct 194 ms 39884 KB Output is correct
26 Correct 128 ms 39844 KB Output is correct
27 Correct 325 ms 44636 KB Output is correct
28 Correct 72 ms 39676 KB Output is correct
29 Correct 392 ms 44792 KB Output is correct
30 Correct 366 ms 43160 KB Output is correct
31 Correct 85 ms 39888 KB Output is correct
32 Correct 132 ms 39792 KB Output is correct
33 Correct 69 ms 39668 KB Output is correct
34 Correct 199 ms 44540 KB Output is correct
35 Correct 86 ms 39756 KB Output is correct
36 Correct 278 ms 44360 KB Output is correct
37 Correct 147 ms 44688 KB Output is correct
38 Correct 222 ms 40048 KB Output is correct
39 Correct 103 ms 39752 KB Output is correct
40 Correct 178 ms 40128 KB Output is correct
41 Correct 152 ms 44552 KB Output is correct
42 Correct 221 ms 39992 KB Output is correct