oj.uz

Submission #722051

# Submission time Handle Problem Language Result Execution time Memory
722051 2023-04-11T11:04:47 Z PoPularPlusPlus Brunhilda’s Birthday (BOI13_brunhilda) C++17
18.7302 / 100
 1000 ms 262144 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;

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);
	vector<pair<int,int>> v;
	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.pb(mp(j , i));
		}
	}
	sv(v);
	int pos = 0;
	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++){
		int pos1 = pos;
		while(pos1 < v.size() && v[pos1].vf == i){
			cur[v[pos].vs] = -1e9;
			pos1++;
		}
		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 << ' ';
		while(pos < pos1){
			q.push(mp(res,v[pos].vs));
			cur[v[pos].vs] = res;
			pos++;
		}
	}
	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:55: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]
   55 |  for(int i = 1; i <= N-2 && pointer < queries.size(); i++){
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   while(pos1 < v.size() && v[pos1].vf == i){
      |         ~~~~~^~~~~~~~~~
brunhilda.cpp:66: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]
   66 |   while(pointer < queries.size()){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 16836 KB Output isn't correct
2 Incorrect 771 ms 131748 KB Output isn't correct
3 Incorrect 455 ms 66100 KB Output isn't correct
4 Correct 53 ms 8640 KB Output is correct
5 Correct 182 ms 33256 KB Output is correct
6 Incorrect 97 ms 16824 KB Output isn't correct
7 Incorrect 438 ms 66112 KB Output isn't correct
8 Incorrect 731 ms 131780 KB Output isn't correct
9 Incorrect 961 ms 131696 KB Output isn't correct
10 Execution timed out 1091 ms 131748 KB Time limit exceeded
11 Incorrect 772 ms 131664 KB Output isn't correct
12 Correct 40 ms 8648 KB Output is correct
13 Runtime error 296 ms 262144 KB Execution killed with signal 9
14 Runtime error 294 ms 262144 KB Execution killed with signal 9
15 Incorrect 701 ms 131748 KB Output isn't correct
16 Incorrect 782 ms 131760 KB Output isn't correct
17 Correct 222 ms 33312 KB Output is correct
18 Correct 57 ms 8704 KB Output is correct

Subtask #2
8.88888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 16828 KB Output is correct
2 Correct 312 ms 37236 KB Output is correct
3 Runtime error 312 ms 262144 KB Execution killed with signal 9
4 Correct 580 ms 66112 KB Output is correct
5 Execution timed out 1084 ms 131928 KB Time limit exceeded
6 Incorrect 541 ms 66108 KB Output isn't correct
7 Correct 242 ms 16916 KB Output is correct
8 Correct 422 ms 66120 KB Output is correct
9 Execution timed out 1090 ms 131940 KB Time limit exceeded
10 Runtime error 313 ms 262144 KB Execution killed with signal 9
11 Runtime error 304 ms 262144 KB Execution killed with signal 9
12 Execution timed out 1088 ms 131752 KB Time limit exceeded
13 Correct 298 ms 33316 KB Output is correct
14 Correct 587 ms 66160 KB Output is correct
15 Runtime error 304 ms 262144 KB Execution killed with signal 9
16 Correct 320 ms 37368 KB Output is correct
17 Runtime error 303 ms 262144 KB Execution killed with signal 9
18 Runtime error 309 ms 262144 KB Execution killed with signal 9

Subtask #3
4.28571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 314 ms 262144 KB Execution killed with signal 9
2 Runtime error 306 ms 262144 KB Execution killed with signal 9
3 Runtime error 312 ms 262144 KB Execution killed with signal 9
4 Execution timed out 1103 ms 132396 KB Time limit exceeded
5 Correct 373 ms 34360 KB Output is correct
6 Runtime error 312 ms 262144 KB Execution killed with signal 9
7 Execution timed out 1082 ms 132592 KB Time limit exceeded
8 Runtime error 310 ms 262144 KB Execution killed with signal 9
9 Runtime error 308 ms 262144 KB Execution killed with signal 9
10 Execution timed out 1081 ms 131900 KB Time limit exceeded
11 Execution timed out 1030 ms 131976 KB Time limit exceeded
12 Runtime error 307 ms 262144 KB Execution killed with signal 9
13 Runtime error 318 ms 262144 KB Execution killed with signal 9
14 Runtime error 307 ms 262144 KB Execution killed with signal 9
15 Runtime error 316 ms 262144 KB Execution killed with signal 9
16 Runtime error 309 ms 262144 KB Execution killed with signal 9
17 Execution timed out 1106 ms 132036 KB Time limit exceeded
18 Runtime error 312 ms 262144 KB Execution killed with signal 9
19 Incorrect 466 ms 66184 KB Output isn't correct
20 Runtime error 310 ms 262144 KB Execution killed with signal 9
21 Runtime error 303 ms 262144 KB Execution killed with signal 9
22 Runtime error 329 ms 262144 KB Execution killed with signal 9
23 Correct 414 ms 34104 KB Output is correct
24 Incorrect 276 ms 17516 KB Output isn't correct
25 Execution timed out 1100 ms 132468 KB Time limit exceeded
26 Execution timed out 1089 ms 132424 KB Time limit exceeded
27 Runtime error 318 ms 262144 KB Execution killed with signal 9
28 Incorrect 445 ms 34676 KB Output isn't correct
29 Execution timed out 1092 ms 133156 KB Time limit exceeded
30 Execution timed out 1089 ms 132816 KB Time limit exceeded
31 Incorrect 563 ms 66840 KB Output isn't correct
32 Incorrect 725 ms 66780 KB Output isn't correct
33 Incorrect 181 ms 17468 KB Output isn't correct
34 Execution timed out 1098 ms 132536 KB Time limit exceeded
35 Incorrect 516 ms 66808 KB Output isn't correct
36 Runtime error 324 ms 262144 KB Execution killed with signal 9
37 Correct 382 ms 34460 KB Output is correct
38 Runtime error 318 ms 262144 KB Execution killed with signal 9
39 Incorrect 350 ms 34020 KB Output isn't correct
40 Execution timed out 1091 ms 132532 KB Time limit exceeded
41 Execution timed out 1087 ms 132604 KB Time limit exceeded
42 Runtime error 307 ms 262144 KB Execution killed with signal 9