oj.uz

Submission #335042

# Submission time Handle Problem Language Result Execution time Memory
335042 2020-12-11T00:49:12 Z rqi Brunhilda’s Birthday (BOI13_brunhilda) C++14
19.5238 / 100
 1000 ms 41172 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];
int ans[10000005];
int main() {
	setIO();
	cin >> m >> Q;
	for(int i = 1; i <= m; i++){
		cin >> p[i];
	}

	ans[0] = 0;
	for(int i = 1; i <= 10000000; i++){
		int maxdif = 0;
		for(int j = m; j >= 1; j--){
			if(p[j] <= maxdif) break;
			ckmax(maxdif, i % p[j]);
		}
		if(maxdif == 0){
			ans[i] = MOD;
		}
		else{
			ans[i] = ans[i-maxdif]+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
16.6666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 39532 KB Output is correct
2 Correct 648 ms 39528 KB Output is correct
3 Correct 179 ms 39532 KB Output is correct
4 Correct 593 ms 39788 KB Output is correct
5 Correct 360 ms 39532 KB Output is correct
6 Correct 220 ms 39680 KB Output is correct
7 Correct 178 ms 39532 KB Output is correct
8 Correct 172 ms 39532 KB Output is correct
9 Correct 210 ms 39532 KB Output is correct
10 Correct 230 ms 39532 KB Output is correct
11 Correct 251 ms 39532 KB Output is correct
12 Execution timed out 1098 ms 35812 KB Time limit exceeded
13 Execution timed out 1097 ms 16748 KB Time limit exceeded
14 Execution timed out 1096 ms 16108 KB Time limit exceeded
15 Correct 490 ms 39532 KB Output is correct
16 Correct 644 ms 39532 KB Output is correct
17 Correct 490 ms 39532 KB Output is correct
18 Correct 594 ms 39656 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 748 KB Time limit exceeded
2 Execution timed out 1095 ms 1516 KB Time limit exceeded
3 Execution timed out 1099 ms 1132 KB Time limit exceeded
4 Execution timed out 1043 ms 1004 KB Time limit exceeded
5 Execution timed out 1088 ms 876 KB Time limit exceeded
6 Execution timed out 1094 ms 9068 KB Time limit exceeded
7 Execution timed out 1042 ms 676 KB Time limit exceeded
8 Execution timed out 1098 ms 16748 KB Time limit exceeded
9 Execution timed out 1039 ms 1392 KB Time limit exceeded
10 Execution timed out 1091 ms 1260 KB Time limit exceeded
11 Execution timed out 1091 ms 876 KB Time limit exceeded
12 Execution timed out 1095 ms 4920 KB Time limit exceeded
13 Execution timed out 1096 ms 764 KB Time limit exceeded
14 Execution timed out 1039 ms 1132 KB Time limit exceeded
15 Execution timed out 1091 ms 876 KB Time limit exceeded
16 Execution timed out 1080 ms 1516 KB Time limit exceeded
17 Execution timed out 1086 ms 16580 KB Time limit exceeded
18 Execution timed out 1092 ms 1772 KB Time limit exceeded

Subtask #3
2.85714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 1132 KB Time limit exceeded
2 Execution timed out 1060 ms 1388 KB Time limit exceeded
3 Execution timed out 1098 ms 1132 KB Time limit exceeded
4 Execution timed out 1086 ms 1132 KB Time limit exceeded
5 Execution timed out 1063 ms 1772 KB Time limit exceeded
6 Execution timed out 1085 ms 1004 KB Time limit exceeded
7 Execution timed out 1093 ms 1644 KB Time limit exceeded
8 Execution timed out 1093 ms 1260 KB Time limit exceeded
9 Execution timed out 1089 ms 1132 KB Time limit exceeded
10 Execution timed out 1089 ms 748 KB Time limit exceeded
11 Execution timed out 1091 ms 1056 KB Time limit exceeded
12 Execution timed out 1092 ms 748 KB Time limit exceeded
13 Execution timed out 1087 ms 1132 KB Time limit exceeded
14 Correct 444 ms 40812 KB Output is correct
15 Execution timed out 1095 ms 876 KB Time limit exceeded
16 Execution timed out 1093 ms 748 KB Time limit exceeded
17 Execution timed out 1098 ms 876 KB Time limit exceeded
18 Execution timed out 1097 ms 1132 KB Time limit exceeded
19 Execution timed out 1092 ms 592 KB Time limit exceeded
20 Execution timed out 1098 ms 1132 KB Time limit exceeded
21 Correct 468 ms 41172 KB Output is correct
22 Execution timed out 1088 ms 1772 KB Time limit exceeded
23 Execution timed out 1093 ms 876 KB Time limit exceeded
24 Execution timed out 1050 ms 9220 KB Time limit exceeded
25 Execution timed out 1089 ms 2716 KB Time limit exceeded
26 Execution timed out 1092 ms 1132 KB Time limit exceeded
27 Execution timed out 1098 ms 1772 KB Time limit exceeded
28 Execution timed out 1099 ms 20716 KB Time limit exceeded
29 Execution timed out 1092 ms 1772 KB Time limit exceeded
30 Execution timed out 1095 ms 1388 KB Time limit exceeded
31 Execution timed out 1095 ms 708 KB Time limit exceeded
32 Execution timed out 1094 ms 1388 KB Time limit exceeded
33 Execution timed out 1094 ms 2540 KB Time limit exceeded
34 Execution timed out 1068 ms 1792 KB Time limit exceeded
35 Execution timed out 1070 ms 5340 KB Time limit exceeded
36 Execution timed out 1084 ms 1772 KB Time limit exceeded
37 Execution timed out 1093 ms 1684 KB Time limit exceeded
38 Execution timed out 1094 ms 748 KB Time limit exceeded
39 Execution timed out 1060 ms 1516 KB Time limit exceeded
40 Execution timed out 1086 ms 748 KB Time limit exceeded
41 Execution timed out 1047 ms 1644 KB Time limit exceeded
42 Execution timed out 1067 ms 12184 KB Time limit exceeded