oj.uz

Submission #335220

# Submission time Handle Problem Language Result Execution time Memory
335220 2020-12-11T15:00:35 Z rqi Brunhilda’s Birthday (BOI13_brunhilda) C++14
43.4921 / 100
 1000 ms 80360 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<bool> vb; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
constexpr int pct(int x) { return __builtin_popcount(x); } 
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll half(ll x) { return fdiv(x,2); }

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
	// note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi);
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi+1);
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
template<class T> void remDup(vector<T>& v) { 
	sort(all(v)); v.erase(unique(all(v)),end(v)); }

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
template<class A> str ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}
template<class A, class B> str ts(pair<A,B> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

int m, Q;
int p[100005];

const int mx = 10000005;
int curlef;
priority_queue<pi, vpi, greater<pi>> pq;
int mults[mx];
int ans[mx];

int main() {
	setIO();

	//clock_t c = clock();
	cin >> m >> Q;
	ll maxval = 1;
	for(int i = 1; i <= m; i++){
		cin >> p[i];
		maxval*=p[i];
		ckmin(maxval, ll(MOD));
	}

	curlef = 0;
	for(int i = 1; i <= m; i++){
		pq.push(mp(p[i], 0));
		mults[0]++;
	}
	ans[0] = 0;

	for(int i = 1; i <= min(maxval, ll(10000000)); i++){
		while(sz(pq) && pq.top().f == i){
			pi a = pq.top();
			pq.pop();
			int lastpos = a.s;
			int nexpos = i+(i-lastpos);

			mults[lastpos]--;
			mults[i]++;

			if(nexpos < mx){
				pq.push(mp(nexpos, i));
			}
		}

		while(curlef <= i){
			if(mults[curlef] > 0) break;
			curlef++;
		}

		if(curlef == i){
			ans[i] = MOD;
		}
		else{
			ans[i] = ans[curlef]+1;
		}

	}

	for(int i = 1; i <= Q; i++){
		int n;
		cin >> n;
		if(n >= maxval){
			ps("oo");
		}
		else ps(ans[n]);
	}
	// cout << fixed << setprecision(5);
	// cout << double(clock()-c)/CLOCKS_PER_SEC;
	// you should actually read the stuff at the bottom
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Compilation message

brunhilda.cpp: In function 'void setIn(str)':
brunhilda.cpp:168:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  168 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp: In function 'void setOut(str)':
brunhilda.cpp:169:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  169 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 610 ms 78868 KB Output is correct
3 Correct 12 ms 2412 KB Output is correct
4 Correct 162 ms 78700 KB Output is correct
5 Correct 270 ms 78652 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 12 ms 2412 KB Output is correct
8 Correct 47 ms 7404 KB Output is correct
9 Correct 762 ms 78680 KB Output is correct
10 Correct 941 ms 78656 KB Output is correct
11 Correct 725 ms 78712 KB Output is correct
12 Correct 140 ms 78580 KB Output is correct
13 Execution timed out 1086 ms 39020 KB Time limit exceeded
14 Execution timed out 1087 ms 38104 KB Time limit exceeded
15 Correct 634 ms 78572 KB Output is correct
16 Correct 607 ms 78672 KB Output is correct
17 Correct 335 ms 78700 KB Output is correct
18 Correct 164 ms 78700 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 78956 KB Output is correct
2 Correct 494 ms 80104 KB Output is correct
3 Execution timed out 1091 ms 25232 KB Time limit exceeded
4 Correct 658 ms 78828 KB Output is correct
5 Execution timed out 1093 ms 45676 KB Time limit exceeded
6 Correct 619 ms 78956 KB Output is correct
7 Correct 371 ms 78956 KB Output is correct
8 Correct 543 ms 78828 KB Output is correct
9 Execution timed out 1094 ms 35516 KB Time limit exceeded
10 Execution timed out 1090 ms 25612 KB Time limit exceeded
11 Execution timed out 1057 ms 25964 KB Time limit exceeded
12 Execution timed out 1103 ms 72172 KB Time limit exceeded
13 Correct 351 ms 78700 KB Output is correct
14 Correct 656 ms 78828 KB Output is correct
15 Execution timed out 1037 ms 30920 KB Time limit exceeded
16 Correct 483 ms 79976 KB Output is correct
17 Execution timed out 1092 ms 36460 KB Time limit exceeded
18 Execution timed out 1088 ms 36724 KB Time limit exceeded

Subtask #3
15.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 31852 KB Time limit exceeded
2 Execution timed out 1093 ms 25452 KB Time limit exceeded
3 Execution timed out 1091 ms 25464 KB Time limit exceeded
4 Execution timed out 1088 ms 64212 KB Time limit exceeded
5 Correct 615 ms 80360 KB Output is correct
6 Execution timed out 1089 ms 39276 KB Time limit exceeded
7 Execution timed out 1062 ms 49768 KB Time limit exceeded
8 Execution timed out 1089 ms 32892 KB Time limit exceeded
9 Execution timed out 1067 ms 32304 KB Time limit exceeded
10 Execution timed out 1050 ms 57324 KB Time limit exceeded
11 Execution timed out 1076 ms 79212 KB Time limit exceeded
12 Execution timed out 1098 ms 42348 KB Time limit exceeded
13 Execution timed out 1091 ms 29680 KB Time limit exceeded
14 Execution timed out 1099 ms 79212 KB Time limit exceeded
15 Execution timed out 1098 ms 37100 KB Time limit exceeded
16 Execution timed out 1097 ms 32236 KB Time limit exceeded
17 Execution timed out 1094 ms 39660 KB Time limit exceeded
18 Execution timed out 1092 ms 25324 KB Time limit exceeded
19 Correct 514 ms 78956 KB Output is correct
20 Execution timed out 1032 ms 24088 KB Time limit exceeded
21 Execution timed out 1093 ms 59116 KB Time limit exceeded
22 Execution timed out 1088 ms 26316 KB Time limit exceeded
23 Correct 625 ms 79472 KB Output is correct
24 Correct 341 ms 79084 KB Output is correct
25 Execution timed out 1097 ms 59172 KB Time limit exceeded
26 Execution timed out 1076 ms 63532 KB Time limit exceeded
27 Execution timed out 1093 ms 23648 KB Time limit exceeded
28 Correct 450 ms 79084 KB Output is correct
29 Execution timed out 1097 ms 35048 KB Time limit exceeded
30 Execution timed out 1096 ms 40680 KB Time limit exceeded
31 Correct 597 ms 79212 KB Output is correct
32 Correct 782 ms 79284 KB Output is correct
33 Correct 243 ms 79084 KB Output is correct
34 Execution timed out 1100 ms 51304 KB Time limit exceeded
35 Correct 554 ms 79212 KB Output is correct
36 Execution timed out 1097 ms 27368 KB Time limit exceeded
37 Correct 619 ms 80360 KB Output is correct
38 Execution timed out 1099 ms 39404 KB Time limit exceeded
39 Correct 442 ms 79212 KB Output is correct
40 Execution timed out 1055 ms 46444 KB Time limit exceeded
41 Execution timed out 1098 ms 51816 KB Time limit exceeded
42 Execution timed out 1094 ms 34028 KB Time limit exceeded