oj.uz

Submission #320032

# Submission time Handle Problem Language Result Execution time Memory
320032 2020-11-07T10:50:13 Z Hemimor Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.88889 / 100
 677 ms 114960 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));
			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
8.88888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 32996 KB Output is correct
2 Runtime error 271 ms 102116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 118 ms 47332 KB Output is correct
4 Runtime error 79 ms 60648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 74 ms 35940 KB Output is correct
6 Correct 45 ms 32996 KB Output is correct
7 Correct 116 ms 47464 KB Output is correct
8 Correct 159 ms 51300 KB Output is correct
9 Correct 232 ms 53480 KB Output is correct
10 Runtime error 331 ms 109988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 202 ms 49764 KB Output is correct
12 Runtime error 83 ms 59496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 588 ms 114960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 570 ms 114788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 264 ms 100632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 259 ms 101988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 137 ms 72420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 82 ms 60644 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 56568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 21 ms 9068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 17 ms 8940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 176 ms 77980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 16 ms 8812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 201 ms 88420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 55 ms 56292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 177 ms 78180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 18 ms 8940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 18 ms 8940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 64 ms 57740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 334 ms 100196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 66 ms 58980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 174 ms 77924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 62 ms 58724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 21 ms 9068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 589 ms 107824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 22 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 59 ms 56416 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 62 ms 56932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 394 ms 97508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 26 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 471 ms 99300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 22 ms 9192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 60 ms 56324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 61 ms 56292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 334 ms 94052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 260 ms 88160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 489 ms 102116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 71 ms 59236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 366 ms 111240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 607 ms 106708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 677 ms 107504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 64 ms 58852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 70 ms 60836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 54 ms 56660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 60 ms 57320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 440 ms 113764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 23 ms 9316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 59 ms 56300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 105 ms 65936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 391 ms 100728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 349 ms 97492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 22 ms 9316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 131 ms 72376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 22 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 61 ms 56676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 117 ms 67940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 224 ms 82148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 78 ms 60696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 22 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 140 ms 72932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 22 ms 9356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 23 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 518 ms 99412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 117 ms 68068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 368 ms 91780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 25 ms 9452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 638 ms 111076 KB Execution killed with signal 11 (could be triggered by violating memory limits)