oj.uz

Submission #320033

# Submission time Handle Problem Language Result Execution time Memory
320033 2020-11-07T10:50:39 Z Hemimor Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 714 ms 113892 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=1000001;
int n,q,res[M];
vi a;

int main(){
	scanf("%d%d",&n,&q);
	a=vi(n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	int mx=a[n-1];
	fill(res,res+mx,1);
	fill(res+mx,res+M,inf);
	multiset<int> st;
	vvi b(M);
	for(auto i:a){
		st.insert(1);
		b[(mx+i-1)/i*i].push_back(i);
	}
	for(int i=mx;i<M;i++){
		for(auto j:b[i]){
			int x=res[i-j];
			st.erase(st.find(x));
			if(i+j<M) b[i+j].push_back(j);
		}
		if(!st.empty()) res[i]=min(inf,1+*st.begin());
		for(auto j:b[i]) st.insert(res[i]);
	}
	for(int i=0;i<q;i++){
		int x;
		scanf("%d",&x);
		if(res[x]==inf) printf("oo\n");
		else printf("%d\n",res[x]);
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:62:12: warning: unused variable 'j' [-Wunused-variable]
   62 |   for(auto j:b[i]) st.insert(res[i]);
      |            ^
brunhilda.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
brunhilda.cpp:45:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  for(int i=0;i<n;i++) scanf("%d",&a[i]);
      |                       ~~~~~^~~~~~~~~~~~
brunhilda.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33244 KB Output is correct
2 Correct 210 ms 50404 KB Output is correct
3 Correct 117 ms 47336 KB Output is correct
4 Correct 47 ms 30224 KB Output is correct
5 Correct 78 ms 35972 KB Output is correct
6 Correct 49 ms 33048 KB Output is correct
7 Correct 118 ms 47440 KB Output is correct
8 Correct 168 ms 51284 KB Output is correct
9 Correct 235 ms 53476 KB Output is correct
10 Correct 266 ms 54372 KB Output is correct
11 Correct 205 ms 49876 KB Output is correct
12 Correct 39 ms 29420 KB Output is correct
13 Correct 521 ms 57044 KB Output is correct
14 Correct 521 ms 57188 KB Output is correct
15 Correct 197 ms 49848 KB Output is correct
16 Correct 201 ms 50616 KB Output is correct
17 Correct 93 ms 35940 KB Output is correct
18 Correct 45 ms 30172 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 56408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 22 ms 9100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 18 ms 8936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 189 ms 80100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 15 ms 8924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 219 ms 91200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 54 ms 56404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 133 ms 39124 KB Output isn't correct
9 Runtime error 17 ms 8932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 9052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 63 ms 57828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 300 ms 50820 KB Output isn't correct
13 Runtime error 96 ms 64100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 184 ms 80100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 63 ms 58596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 30 ms 9068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 574 ms 54884 KB Output isn't correct
18 Runtime error 20 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 56292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 70 ms 60644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 58 ms 56932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 451 ms 101860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 26 ms 9212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 556 ms 105860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 9344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 59 ms 56292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 59 ms 56292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 364 ms 97856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 285 ms 91360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 555 ms 106852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 65 ms 59236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 366 ms 111236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 651 ms 110768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 714 ms 111580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 64 ms 58724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 74 ms 60644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 59 ms 56420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 63 ms 56960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 466 ms 113892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 25 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 56 ms 56164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 108 ms 66660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 389 ms 102584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 385 ms 101732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 21 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 141 ms 74212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 21 ms 9188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 62 ms 56544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 152 ms 73572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 214 ms 84324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 86 ms 61668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 20 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Incorrect 142 ms 38496 KB Output isn't correct
36 Runtime error 19 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 21 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 585 ms 106084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 144 ms 69604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 430 ms 99940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 23 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Incorrect 622 ms 56932 KB Output isn't correct