oj.uz

Submission #51532

# Submission time Handle Problem Language Result Execution time Memory
51532 2018-06-18T07:27:10 Z WA_TLE Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 45 ms 39504 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	//信じる気持ちさえあればなんとかなる
	int i,m,q;cin>>m>>q;
	vector<int>sosu(m);
	for(i=0;i<m;i++){cin>>sosu[i];}
	vector<int>anss;
	anss.pub(0);
	int gen=0;
	while(-1){
		int nex=gen;
		for(auto it:sosu){
			maxeq(nex,((gen/it +1)*it)-1);
		}
		if(nex==gen){break;}
		anss.pub(nex);
		gen=nex;
		if(gen>1e7+10){break;}
	}
	while(q--){
		int in;cin>>in;
		int turn=LBI(anss,in);
		if(anss.size()==turn){cout<<"oo\n";}
		else{cout<<turn<<"\n";}
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(anss.size()==turn){cout<<"oo\n";}
      ~~~~~~~~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 7 ms 752 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Correct 6 ms 752 KB Output is correct
5 Correct 14 ms 1896 KB Output is correct
6 Correct 4 ms 1896 KB Output is correct
7 Correct 4 ms 1896 KB Output is correct
8 Correct 4 ms 1896 KB Output is correct
9 Correct 16 ms 2968 KB Output is correct
10 Correct 10 ms 2968 KB Output is correct
11 Correct 12 ms 2968 KB Output is correct
12 Correct 4 ms 2968 KB Output is correct
13 Correct 7 ms 2968 KB Output is correct
14 Correct 9 ms 2968 KB Output is correct
15 Correct 6 ms 2968 KB Output is correct
16 Correct 7 ms 2968 KB Output is correct
17 Correct 11 ms 2968 KB Output is correct
18 Correct 7 ms 2968 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2968 KB Output is correct
2 Correct 16 ms 2968 KB Output is correct
3 Correct 13 ms 2968 KB Output is correct
4 Correct 4 ms 2968 KB Output is correct
5 Correct 10 ms 2968 KB Output is correct
6 Correct 3 ms 2968 KB Output is correct
7 Correct 4 ms 2968 KB Output is correct
8 Correct 4 ms 2968 KB Output is correct
9 Correct 13 ms 3576 KB Output is correct
10 Correct 12 ms 3944 KB Output is correct
11 Correct 10 ms 4160 KB Output is correct
12 Correct 4 ms 4160 KB Output is correct
13 Correct 3 ms 4160 KB Output is correct
14 Correct 5 ms 4160 KB Output is correct
15 Correct 11 ms 4476 KB Output is correct
16 Correct 19 ms 5396 KB Output is correct
17 Correct 7 ms 5396 KB Output is correct
18 Correct 25 ms 6216 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6716 KB Output is correct
2 Correct 17 ms 7236 KB Output is correct
3 Correct 29 ms 8208 KB Output is correct
4 Correct 45 ms 8660 KB Output is correct
5 Correct 35 ms 10636 KB Output is correct
6 Correct 32 ms 11012 KB Output is correct
7 Correct 27 ms 12432 KB Output is correct
8 Correct 19 ms 12824 KB Output is correct
9 Correct 18 ms 13472 KB Output is correct
10 Correct 8 ms 13472 KB Output is correct
11 Correct 10 ms 13624 KB Output is correct
12 Correct 11 ms 13800 KB Output is correct
13 Correct 35 ms 15028 KB Output is correct
14 Correct 36 ms 16448 KB Output is correct
15 Correct 12 ms 16448 KB Output is correct
16 Correct 12 ms 16448 KB Output is correct
17 Correct 13 ms 16448 KB Output is correct
18 Correct 17 ms 17012 KB Output is correct
19 Correct 10 ms 17036 KB Output is correct
20 Correct 21 ms 18004 KB Output is correct
21 Correct 41 ms 19284 KB Output is correct
22 Correct 37 ms 20572 KB Output is correct
23 Correct 29 ms 21292 KB Output is correct
24 Correct 32 ms 22020 KB Output is correct
25 Correct 40 ms 22756 KB Output is correct
26 Correct 30 ms 23368 KB Output is correct
27 Correct 28 ms 24728 KB Output is correct
28 Correct 27 ms 25332 KB Output is correct
29 Correct 40 ms 27144 KB Output is correct
30 Correct 35 ms 28320 KB Output is correct
31 Correct 25 ms 28860 KB Output is correct
32 Correct 30 ms 29440 KB Output is correct
33 Correct 25 ms 30164 KB Output is correct
34 Correct 27 ms 31628 KB Output is correct
35 Correct 26 ms 32148 KB Output is correct
36 Correct 37 ms 33828 KB Output is correct
37 Correct 44 ms 35432 KB Output is correct
38 Correct 28 ms 35852 KB Output is correct
39 Correct 28 ms 36664 KB Output is correct
40 Correct 29 ms 37440 KB Output is correct
41 Correct 25 ms 38864 KB Output is correct
42 Correct 30 ms 39504 KB Output is correct