oj.uz

Submission #722048

# Submission time Handle Problem Language Result Execution time Memory
722048 2023-04-11T11:00:12 Z PoPularPlusPlus Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 56 ms 11228 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 = 100002;
vector<int> v[N];

void solve(){
	int n , qu;
	cin >> n >> qu;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	vector<pair<int,int>> queries(qu);
	for(int i = 0; i < qu; i++){
		cin >> queries[i].vf;
		queries[i].vs = i;
	}
	sort(all(queries));
	int mx = 0;
	for(int i = 0; i < n; i++)mx = max(mx , arr[i]);
	for(int i = 0; i < n; i++){
		for(int j = arr[i]; j <= N-2; j+=arr[i]){
			v[j].pb(i);
		}
	}
	int cur[n];
	queue<pair<int,int>> q;
	for(int i = 0; i < n; i++){
		cur[i] = 0;
		q.push(mp(0,i));
	}
	int ans[qu];
	int pointer = 0;
	for(int i = 1; i <= N-2 && pointer < queries.size(); i++){
		for(int j : v[i]){
			cur[j] = -1e9;
		}
		while(q.size()){
			pair<int,int> p = q.front();
			if(cur[p.vs] == p.vf)break;
			q.pop();
		}
		while(pointer < queries.size()){
			if(queries[pointer].vf == i){
				ans[queries[pointer].vs] = (q.size() ? q.front().vf+1 : 1e9);
			}
			else break;
			pointer++;
		}
		int res = 1e9;
		if(q.size())res = q.front().vf+1;
		//cout << res << ' ';
		for(int j : v[i]){
			if(cur[j] == -1e9){
				q.push(mp(res,j));
				cur[j] = res;
			}
		}
	}
	for(int i = 0; i < qu; i++){
		if(ans[i] >= 1e9)cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

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

Compilation message

brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 1; i <= N-2 && pointer < queries.size(); i++){
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   while(pointer < queries.size()){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 6 ms 4628 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 9 ms 4564 KB Output is correct
8 Correct 7 ms 4908 KB Output is correct
9 Correct 8 ms 5204 KB Output is correct
10 Correct 9 ms 5332 KB Output is correct
11 Correct 9 ms 4820 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 15 ms 5748 KB Output is correct
14 Correct 17 ms 5844 KB Output is correct
15 Correct 7 ms 4820 KB Output is correct
16 Correct 7 ms 4948 KB Output is correct
17 Correct 5 ms 3540 KB Output is correct
18 Correct 4 ms 3028 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3284 KB Output isn't correct
2 Incorrect 15 ms 4816 KB Output isn't correct
3 Incorrect 26 ms 8828 KB Output isn't correct
4 Incorrect 7 ms 4328 KB Output isn't correct
5 Incorrect 17 ms 6980 KB Output isn't correct
6 Incorrect 7 ms 4976 KB Output isn't correct
7 Incorrect 4 ms 3284 KB Output isn't correct
8 Incorrect 6 ms 3924 KB Output isn't correct
9 Incorrect 24 ms 7716 KB Output isn't correct
10 Incorrect 31 ms 8876 KB Output isn't correct
11 Incorrect 28 ms 8312 KB Output isn't correct
12 Incorrect 11 ms 5664 KB Output isn't correct
13 Incorrect 6 ms 3680 KB Output isn't correct
14 Incorrect 7 ms 4308 KB Output isn't correct
15 Incorrect 21 ms 7808 KB Output isn't correct
16 Incorrect 13 ms 4820 KB Output isn't correct
17 Incorrect 20 ms 6828 KB Output isn't correct
18 Incorrect 24 ms 8304 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8820 KB Output isn't correct
2 Incorrect 33 ms 8916 KB Output isn't correct
3 Incorrect 39 ms 9560 KB Output isn't correct
4 Incorrect 33 ms 8140 KB Output isn't correct
5 Incorrect 38 ms 6660 KB Output isn't correct
6 Incorrect 39 ms 9036 KB Output isn't correct
7 Incorrect 28 ms 8012 KB Output isn't correct
8 Incorrect 29 ms 8816 KB Output isn't correct
9 Incorrect 30 ms 8848 KB Output isn't correct
10 Incorrect 14 ms 6256 KB Output isn't correct
11 Incorrect 17 ms 5716 KB Output isn't correct
12 Incorrect 23 ms 7580 KB Output isn't correct
13 Incorrect 35 ms 9696 KB Output isn't correct
14 Incorrect 28 ms 7412 KB Output isn't correct
15 Incorrect 23 ms 7628 KB Output isn't correct
16 Incorrect 23 ms 7744 KB Output isn't correct
17 Incorrect 19 ms 7236 KB Output isn't correct
18 Incorrect 31 ms 8936 KB Output isn't correct
19 Incorrect 11 ms 4748 KB Output isn't correct
20 Incorrect 39 ms 9648 KB Output isn't correct
21 Incorrect 32 ms 7488 KB Output isn't correct
22 Incorrect 56 ms 11228 KB Output isn't correct
23 Incorrect 33 ms 5860 KB Output isn't correct
24 Incorrect 26 ms 5452 KB Output isn't correct
25 Incorrect 37 ms 7628 KB Output isn't correct
26 Incorrect 37 ms 8060 KB Output isn't correct
27 Incorrect 43 ms 10480 KB Output isn't correct
28 Incorrect 22 ms 6212 KB Output isn't correct
29 Incorrect 53 ms 10088 KB Output isn't correct
30 Incorrect 44 ms 9304 KB Output isn't correct
31 Incorrect 36 ms 5992 KB Output isn't correct
32 Incorrect 29 ms 6576 KB Output isn't correct
33 Incorrect 24 ms 4924 KB Output isn't correct
34 Incorrect 28 ms 8020 KB Output isn't correct
35 Incorrect 22 ms 6260 KB Output isn't correct
36 Incorrect 50 ms 10948 KB Output isn't correct
37 Incorrect 37 ms 6656 KB Output isn't correct
38 Incorrect 41 ms 9080 KB Output isn't correct
39 Incorrect 29 ms 5616 KB Output isn't correct
40 Incorrect 35 ms 8476 KB Output isn't correct
41 Incorrect 28 ms 8496 KB Output isn't correct
42 Incorrect 40 ms 8784 KB Output isn't correct