oj.uz

Submission #320031

# Submission time Handle Problem Language Result Execution time Memory
320031 2020-11-07T10:44:37 Z Hemimor Brunhilda’s Birthday (BOI13_brunhilda) C++14
6.66667 / 100
 669 ms 114932 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]=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
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 32996 KB Output isn't correct
2 Runtime error 262 ms 102192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 119 ms 47332 KB Output is correct
4 Runtime error 79 ms 60644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 73 ms 35940 KB Output is correct
6 Incorrect 45 ms 32996 KB Output isn't correct
7 Correct 116 ms 47336 KB Output is correct
8 Correct 169 ms 51300 KB Output is correct
9 Correct 242 ms 53604 KB Output is correct
10 Runtime error 350 ms 110052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 226 ms 49636 KB Output is correct
12 Runtime error 72 ms 59492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 601 ms 114932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 572 ms 114788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 250 ms 100580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 256 ms 102016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 128 ms 72420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 80 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 57 ms 56696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 22 ms 9824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 18 ms 9452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 183 ms 77924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 18 ms 9188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 200 ms 88424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 54 ms 56420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 169 ms 78180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 9444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 18 ms 9580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 59 ms 57828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 347 ms 100324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 67 ms 59108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 176 ms 77920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 66 ms 58984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 22 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 573 ms 107688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 24 ms 9964 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 56804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 71 ms 61028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 61 ms 57444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 350 ms 97508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 30 ms 10092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 488 ms 99556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 23 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 59 ms 56804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 59 ms 56808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 340 ms 94304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 252 ms 88312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 500 ms 102500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 62 ms 59656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 367 ms 111460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 593 ms 106680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 669 ms 107752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 64 ms 59108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 69 ms 61028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 53 ms 56548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 57444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 445 ms 113964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 23 ms 10092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 56 ms 56548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 102 ms 65760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 372 ms 100580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 368 ms 97644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 23 ms 10088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 131 ms 72164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 22 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 63 ms 57188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 132 ms 67812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 197 ms 82276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 76 ms 60516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 22 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 138 ms 73060 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 21 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 23 ms 10092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 493 ms 99552 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 357 ms 91876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 23 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 619 ms 110944 KB Execution killed with signal 11 (could be triggered by violating memory limits)