oj.uz

답안 #335221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335221 2020-12-11T15:16:11 Z rqi Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 1000 ms 81260 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 n[100005];

const int mx = 10000005;
int curlef;
priority_queue<pi> pq;
int mults[mx];
bitset<mx> process;
int ans[mx]; //best transition

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));
	}

	int start = 0;

	for(int i = 1; i <= Q; i++){
		cin >> n[i];
		process[n[i]] = 1;
		ckmax(start, n[i]);
	}
	ckmin(start, int(maxval-1));

	curlef = start;
	for(int i = 1; i <= m; i++){
		int curpos = start/p[i]*p[i];
		ckmin(curlef, curpos);
		mults[curpos]++;
		pq.push(mp(curpos-p[i], p[i]));
	}

	for(int i = start; i >= 1; i--){
		if(!process[i]) continue;
		while(pq.top().f > i){
			pi a = pq.top();
			pq.pop();
			int newpos = i/a.s*a.s;
			ckmin(curlef, newpos);
			mults[a.f]--;
			mults[newpos]++;
			pq.push(mp(newpos-a.s, a.s)); 
		}
		ans[i] = curlef;
		process[ans[i]] = 1;
	}

	ans[0] = 0;
	for(int i = 1; i < start; i++){
		if(process[i]) ans[i] = ans[ans[i]]+1;
	}

	for(int i = 1; i <= Q; i++){
		if(n[i] >= maxval){
			ps("oo");
		}
		else ps(ans[n[i]]);
	}
	// 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Incorrect 3 ms 492 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 492 KB Output isn't correct
8 Incorrect 1 ms 492 KB Output isn't correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Incorrect 1 ms 512 KB Output isn't correct
11 Incorrect 1 ms 492 KB Output isn't correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Incorrect 2 ms 492 KB Output isn't correct
14 Incorrect 5 ms 492 KB Output isn't correct
15 Incorrect 1 ms 492 KB Output isn't correct
16 Incorrect 1 ms 492 KB Output isn't correct
17 Incorrect 4 ms 492 KB Output isn't correct
18 Incorrect 3 ms 492 KB Output isn't correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 37996 KB Output isn't correct
2 Incorrect 62 ms 32508 KB Output isn't correct
3 Incorrect 54 ms 16636 KB Output isn't correct
4 Incorrect 63 ms 36476 KB Output isn't correct
5 Incorrect 25 ms 10092 KB Output isn't correct
6 Incorrect 19 ms 14188 KB Output isn't correct
7 Incorrect 60 ms 38016 KB Output isn't correct
8 Incorrect 27 ms 15980 KB Output isn't correct
9 Incorrect 31 ms 10344 KB Output isn't correct
10 Incorrect 54 ms 16488 KB Output isn't correct
11 Incorrect 128 ms 38508 KB Output isn't correct
12 Incorrect 67 ms 35308 KB Output isn't correct
13 Incorrect 46 ms 38380 KB Output isn't correct
14 Incorrect 63 ms 36460 KB Output isn't correct
15 Incorrect 38 ms 12800 KB Output isn't correct
16 Incorrect 61 ms 32488 KB Output isn't correct
17 Incorrect 118 ms 41324 KB Output isn't correct
18 Incorrect 106 ms 29928 KB Output isn't correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 571 ms 64492 KB Output isn't correct
2 Incorrect 999 ms 79576 KB Output isn't correct
3 Incorrect 127 ms 28672 KB Output isn't correct
4 Incorrect 387 ms 81260 KB Output isn't correct
5 Incorrect 142 ms 39912 KB Output isn't correct
6 Incorrect 703 ms 81128 KB Output isn't correct
7 Incorrect 98 ms 26088 KB Output isn't correct
8 Incorrect 557 ms 64236 KB Output isn't correct
9 Incorrect 556 ms 64236 KB Output isn't correct
10 Incorrect 388 ms 75116 KB Output isn't correct
11 Incorrect 344 ms 78316 KB Output isn't correct
12 Incorrect 462 ms 78700 KB Output isn't correct
13 Incorrect 102 ms 20336 KB Output isn't correct
14 Incorrect 160 ms 49772 KB Output isn't correct
15 Incorrect 503 ms 79468 KB Output isn't correct
16 Incorrect 651 ms 78956 KB Output isn't correct
17 Incorrect 660 ms 74348 KB Output isn't correct
18 Incorrect 989 ms 79552 KB Output isn't correct
19 Incorrect 152 ms 77164 KB Output isn't correct
20 Incorrect 126 ms 28652 KB Output isn't correct
21 Incorrect 179 ms 77420 KB Output isn't correct
22 Incorrect 789 ms 60120 KB Output isn't correct
23 Incorrect 260 ms 58352 KB Output isn't correct
24 Incorrect 190 ms 80492 KB Output isn't correct
25 Incorrect 505 ms 81260 KB Output isn't correct
26 Incorrect 384 ms 81132 KB Output isn't correct
27 Incorrect 126 ms 27496 KB Output isn't correct
28 Incorrect 84 ms 41196 KB Output isn't correct
29 Incorrect 783 ms 60100 KB Output isn't correct
30 Incorrect 742 ms 62568 KB Output isn't correct
31 Incorrect 263 ms 80492 KB Output isn't correct
32 Incorrect 323 ms 80656 KB Output isn't correct
33 Incorrect 153 ms 80492 KB Output isn't correct
34 Incorrect 90 ms 26088 KB Output isn't correct
35 Incorrect 92 ms 41580 KB Output isn't correct
36 Execution timed out 1099 ms 79824 KB Time limit exceeded
37 Incorrect 144 ms 39912 KB Output isn't correct
38 Incorrect 697 ms 81228 KB Output isn't correct
39 Incorrect 248 ms 80620 KB Output isn't correct
40 Incorrect 583 ms 81260 KB Output isn't correct
41 Incorrect 54 ms 11752 KB Output isn't correct
42 Incorrect 164 ms 43756 KB Output isn't correct