oj.uz

Submission #335218

# Submission time Handle Problem Language Result Execution time Memory
335218 2020-12-11T14:53:56 Z rqi Brunhilda’s Birthday (BOI13_brunhilda) C++14
43.4921 / 100
 1000 ms 81768 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();
	cin >> m >> Q;
	for(int i = 1; i <= m; i++){
		cin >> p[i];
	}

	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 <= 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(ans[n] >= MOD){
			ps("oo");
		}
		else ps(ans[n]);
	}

	// 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 180 ms 78572 KB Output is correct
2 Correct 598 ms 78848 KB Output is correct
3 Correct 414 ms 78700 KB Output is correct
4 Correct 157 ms 78700 KB Output is correct
5 Correct 271 ms 78572 KB Output is correct
6 Correct 179 ms 78620 KB Output is correct
7 Correct 410 ms 78700 KB Output is correct
8 Correct 512 ms 78700 KB Output is correct
9 Correct 737 ms 78720 KB Output is correct
10 Correct 931 ms 78728 KB Output is correct
11 Correct 720 ms 78700 KB Output is correct
12 Correct 138 ms 78700 KB Output is correct
13 Execution timed out 1088 ms 39564 KB Time limit exceeded
14 Execution timed out 1088 ms 38984 KB Time limit exceeded
15 Correct 618 ms 78700 KB Output is correct
16 Correct 598 ms 78724 KB Output is correct
17 Correct 322 ms 78700 KB Output is correct
18 Correct 159 ms 78700 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 79084 KB Output is correct
2 Correct 486 ms 80616 KB Output is correct
3 Execution timed out 1087 ms 25832 KB Time limit exceeded
4 Correct 653 ms 78700 KB Output is correct
5 Execution timed out 1054 ms 43884 KB Time limit exceeded
6 Correct 600 ms 78744 KB Output is correct
7 Correct 357 ms 78956 KB Output is correct
8 Correct 531 ms 78700 KB Output is correct
9 Execution timed out 1098 ms 36072 KB Time limit exceeded
10 Execution timed out 1056 ms 25320 KB Time limit exceeded
11 Execution timed out 1061 ms 25836 KB Time limit exceeded
12 Execution timed out 1063 ms 70876 KB Time limit exceeded
13 Correct 334 ms 78700 KB Output is correct
14 Correct 649 ms 78704 KB Output is correct
15 Execution timed out 1095 ms 33372 KB Time limit exceeded
16 Correct 474 ms 80616 KB Output is correct
17 Execution timed out 1093 ms 36552 KB Time limit exceeded
18 Execution timed out 1091 ms 37096 KB Time limit exceeded

Subtask #3
15.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 33892 KB Time limit exceeded
2 Execution timed out 1091 ms 25708 KB Time limit exceeded
3 Execution timed out 1057 ms 25324 KB Time limit exceeded
4 Execution timed out 1101 ms 66028 KB Time limit exceeded
5 Correct 616 ms 81696 KB Output is correct
6 Execution timed out 1095 ms 40044 KB Time limit exceeded
7 Execution timed out 1049 ms 49664 KB Time limit exceeded
8 Execution timed out 1052 ms 32484 KB Time limit exceeded
9 Execution timed out 1052 ms 32492 KB Time limit exceeded
10 Execution timed out 1050 ms 58576 KB Time limit exceeded
11 Execution timed out 1071 ms 79212 KB Time limit exceeded
12 Execution timed out 1076 ms 41324 KB Time limit exceeded
13 Execution timed out 1085 ms 29956 KB Time limit exceeded
14 Execution timed out 1095 ms 79980 KB Time limit exceeded
15 Execution timed out 1051 ms 35820 KB Time limit exceeded
16 Execution timed out 1097 ms 32364 KB Time limit exceeded
17 Execution timed out 1097 ms 40556 KB Time limit exceeded
18 Execution timed out 1052 ms 25324 KB Time limit exceeded
19 Correct 503 ms 79084 KB Output is correct
20 Execution timed out 1072 ms 25640 KB Time limit exceeded
21 Execution timed out 1099 ms 59976 KB Time limit exceeded
22 Execution timed out 1049 ms 26188 KB Time limit exceeded
23 Correct 634 ms 80368 KB Output is correct
24 Correct 328 ms 79724 KB Output is correct
25 Execution timed out 1081 ms 58876 KB Time limit exceeded
26 Execution timed out 1095 ms 65900 KB Time limit exceeded
27 Execution timed out 1096 ms 24168 KB Time limit exceeded
28 Correct 450 ms 79724 KB Output is correct
29 Execution timed out 1066 ms 34536 KB Time limit exceeded
30 Execution timed out 1099 ms 40220 KB Time limit exceeded
31 Correct 598 ms 79744 KB Output is correct
32 Correct 772 ms 79724 KB Output is correct
33 Correct 236 ms 79628 KB Output is correct
34 Execution timed out 1091 ms 51560 KB Time limit exceeded
35 Correct 543 ms 79896 KB Output is correct
36 Execution timed out 1097 ms 28136 KB Time limit exceeded
37 Correct 623 ms 81768 KB Output is correct
38 Execution timed out 1047 ms 38380 KB Time limit exceeded
39 Correct 436 ms 79852 KB Output is correct
40 Execution timed out 1046 ms 46452 KB Time limit exceeded
41 Execution timed out 1087 ms 51560 KB Time limit exceeded
42 Execution timed out 1095 ms 34540 KB Time limit exceeded