oj.uz

Submission #925375

# Submission time Handle Problem Language Result Execution time Memory
925375 2024-02-11T13:55:12 Z 8pete8 Brunhilda’s Birthday (BOI13_brunhilda) C++17
77.4603 / 100
 185 ms 79272 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
//#define int long long
const int mod=1e9+7,mxn=1e7+1,lg=30;//inf=1e18,minf=-1e18,Mxn=100000,root=700;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}	
int n,q;
int ans[mxn+1],mx[mxn+1];
int32_t main(){
	//setIO("redistricting");
	fastio
	cin>>n>>q;
	vector<int>v(n);
	for(int i=0;i<n;i++)cin>>v[i];
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	for(auto i:v)for(int j=i-1;j<=mxn;j+=i)mx[j]=max(mx[j],i-1);
	for(int i=mxn;i>=0;i--)mx[i]=max(mx[i],mx[i+1]-1);
	for(int i=1;i<=mxn;i++){
		ans[i]=ans[i-mx[i]];
		if(ans[i]!=-1)ans[i]++;
		if(i<v.back())ans[i]=1;
		if(mx[i]<=0)ans[i]=-1;
	}
	while(q--){
		int g;cin>>g;
		if(ans[g]!=-1)cout<<ans[g]<<'\n';
		else cout<<"oo"<<'\n';
	}
}

Compilation message

brunhilda.cpp: In function 'void setIO(std::string)':
brunhilda.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 78676 KB Output is correct
2 Correct 64 ms 78504 KB Output is correct
3 Correct 63 ms 78504 KB Output is correct
4 Correct 49 ms 78496 KB Output is correct
5 Correct 56 ms 78484 KB Output is correct
6 Correct 56 ms 78500 KB Output is correct
7 Correct 61 ms 78680 KB Output is correct
8 Correct 64 ms 78532 KB Output is correct
9 Correct 71 ms 78484 KB Output is correct
10 Correct 80 ms 78672 KB Output is correct
11 Correct 76 ms 78676 KB Output is correct
12 Correct 48 ms 78564 KB Output is correct
13 Correct 134 ms 78672 KB Output is correct
14 Correct 134 ms 78672 KB Output is correct
15 Correct 73 ms 78676 KB Output is correct
16 Correct 63 ms 78676 KB Output is correct
17 Correct 65 ms 78548 KB Output is correct
18 Correct 49 ms 78560 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 78676 KB Output is correct
2 Correct 65 ms 78928 KB Output is correct
3 Correct 155 ms 78932 KB Output is correct
4 Correct 71 ms 78504 KB Output is correct
5 Correct 111 ms 78728 KB Output is correct
6 Correct 62 ms 78512 KB Output is correct
7 Correct 67 ms 78548 KB Output is correct
8 Correct 66 ms 78676 KB Output is correct
9 Correct 130 ms 78928 KB Output is correct
10 Correct 160 ms 78776 KB Output is correct
11 Incorrect 174 ms 78652 KB Output isn't correct
12 Correct 91 ms 78672 KB Output is correct
13 Correct 52 ms 78676 KB Output is correct
14 Correct 70 ms 78672 KB Output is correct
15 Correct 139 ms 78660 KB Output is correct
16 Correct 69 ms 78928 KB Output is correct
17 Correct 136 ms 78508 KB Output is correct
18 Correct 136 ms 78892 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 79212 KB Output is correct
2 Correct 178 ms 78928 KB Output is correct
3 Correct 176 ms 78948 KB Output is correct
4 Incorrect 121 ms 78932 KB Output isn't correct
5 Incorrect 83 ms 79140 KB Output isn't correct
6 Correct 149 ms 78928 KB Output is correct
7 Correct 121 ms 79184 KB Output is correct
8 Correct 150 ms 78952 KB Output is correct
9 Correct 142 ms 78972 KB Output is correct
10 Correct 110 ms 78672 KB Output is correct
11 Incorrect 95 ms 78756 KB Output isn't correct
12 Correct 133 ms 78672 KB Output is correct
13 Correct 163 ms 78976 KB Output is correct
14 Correct 101 ms 79272 KB Output is correct
15 Incorrect 133 ms 78676 KB Output isn't correct
16 Correct 152 ms 78676 KB Output is correct
17 Correct 132 ms 78932 KB Output is correct
18 Correct 174 ms 78932 KB Output is correct
19 Incorrect 60 ms 78676 KB Output isn't correct
20 Correct 176 ms 78928 KB Output is correct
21 Incorrect 116 ms 79260 KB Output isn't correct
22 Correct 182 ms 79148 KB Output is correct
23 Correct 87 ms 78860 KB Output is correct
24 Correct 73 ms 78932 KB Output is correct
25 Incorrect 126 ms 79012 KB Output isn't correct
26 Incorrect 105 ms 78928 KB Output isn't correct
27 Correct 185 ms 79148 KB Output is correct
28 Incorrect 72 ms 78792 KB Output isn't correct
29 Correct 170 ms 79188 KB Output is correct
30 Correct 155 ms 79188 KB Output is correct
31 Correct 84 ms 78932 KB Output is correct
32 Incorrect 94 ms 78852 KB Output isn't correct
33 Incorrect 66 ms 78860 KB Output isn't correct
34 Correct 131 ms 79184 KB Output is correct
35 Incorrect 75 ms 78932 KB Output isn't correct
36 Correct 173 ms 79184 KB Output is correct
37 Incorrect 90 ms 79184 KB Output isn't correct
38 Correct 146 ms 78932 KB Output is correct
39 Incorrect 81 ms 78932 KB Output isn't correct
40 Correct 121 ms 78932 KB Output is correct
41 Correct 106 ms 79184 KB Output is correct
42 Incorrect 148 ms 78932 KB Output isn't correct