oj.uz

답안 #503775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503775 2022-01-08T21:36:06 Z lobo_prix Akvizna (COCI19_akvizna) C++17
130 / 130
 1052 ms 15204 KB 
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
using namespace std;

#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
using f64=long double; //long double(살짝느림),__float128(매우느림)
#define CPP20 1
#define ARGAUTO 1
#define DBG_SETW 3
//#define CONCEPT

#define pushb(...) push_back({__VA_ARGS__})
#define pushf(...) push_front({__VA_ARGS__})
#define push_(...) push({__VA_ARGS__})
#define popb pop_back
#define popf pop_front
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define cxp constexpr
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define reduce accumulate
#define itos to_string
using i64=long long;using u64=unsigned long long;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=greater<>>using PQ=std::priority_queue<T,vector<T>,CMP>;

#define head(x) (x.begin())
#define tail(x) prev(x.end())

//Handy Funcs
template<class T>int sz(const T& x){return x.size();}
int divc(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
int divf(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
cxp i64 lg2f(i64 x){return 63-__builtin_clzll(x);}
cxp i64 lg2c(i64 x){return 64-__builtin_clzll(x-1);}
template<class T>T sq(T x){return x*x;}

void WARN(bool cond,const char* str){
	#if DEBUG
	static set<const char*> z;
	if(cond&&!z.count(str))z.insert(str),cerr<<"[WARN] "<<str<<endl;
	#endif
}

template<class T>cxp T inf(){return numeric_limits<T>::max()/2;}
#ifdef CONCEPT
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<MemberInf T>T inf(){return T().inf();}
#endif

template<class T, class P=vector<T>>
struct Arr:public P{
	Arr(){P::shrink_to_fit();}
	explicit Arr(signed n):P(n){}
	explicit Arr(signed n,T init):P(n,init){}
	Arr(initializer_list<T>il):P(il){}
#if ARGAUTO
	Arr(auto its, auto ite):P(its,ite){}
#endif
	inline T& operator[](signed i){
		int n=sz(*this);
		if(i<0)i+=n,WARN(1,"Neg Index Found");
		if(i>=n)i-=n,WARN(1,"Over Index Found");
		return P::operator[](i);
	}
	const T& operator[](signed i)const{	
		int n=sz(*this);
		if(i<0)i+=n,WARN(1,"Neg Index Found");
		if(i>=n)i-=n,WARN(1,"Over Index Found");
		return P::operator[](i);
	}
	T& at(signed i){return *this[i];}
	const T& at(signed i)const{return *this[i];}
};
#if ARGAUTO
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}
#endif

#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}

template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
// Arr<int> range(int n){Arr<int> r;while(n--)r.pushb(sz(r));return r;} std::iota써라
template<class T>Arr<pair<int,T>> enumer(const Arr<T>& a){//views::enumerate in c++23
	Arr<pair<int,T>> r;
	for(auto&i:a)r.pushb(sz(r),i);
	return r;
}
Arr<int> permuinv(const Arr<int>& a){
	Arr<int> r(sz(a));
	for(auto [i,v]:enumer(a))r[v]=i;
	return r;
}
Arr<Arr<int>> occur(const Arr<int>& a){
	Arr<Arr<int>> r(*max_element(a.begin(),a.end()));
	for(auto [i,v]:enumer(a))r[v].pushb(i);
	return r;
}

//Consts
// const f64 pi=numbers::pi_v<f64>,eps=FP_EPS;
const f64 pi=acos(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//

class LineException{};
class LineSame:public LineException{};
class LineParallel:public LineException{};

//NOTE: 직선의 방정식과 2by2연립solver
struct Line{
	//ax+by+c=0
	int a,b,c;
	Line(int a,int b,int c):a(a),b(b),c(c){}
	Line(pint a,pint b):Line(a.se-b.se,b.fi-a.fi,-a.se*(b.fi-a.fi)+a.fi*(b.se-a.se)){}
	Line(pint tangent, pint pt, void* dummy_param):Line(pt,mkp(pt.fi+tangent.fi,pt.se-tangent.se)){}
	bool operator==(const Line&r)const{return mkt(a,b,c)==mkt(r.a,r.b,r.c) or mkt(-a,-b,-c)==mkt(r.a,r.b,r.c);}
	pint tan()const{return !b?pint{1,0}:(b>=0?pint{-a,b}:pint{a,-b});}//기울기=[0]/[1]
	tint intersect(const Line& r)const{
		int det=a*r.b-b*r.a;
		if(det==0){//det=0
			if(a*r.c==r.a*c) throw LineSame();//a/r.a==c/r.c
			else throw LineParallel();
		}
		return {(b*r.c-r.b*c),(c*r.a-r.c*a),det};//교점=([0]/[2],[1]/[2])
	}
	tint foot(pint v){return {b*(b*v.fi-a*v.se)-a*c,a*(-b*v.fi+a*v.se)-b*c,a*a+b*b};}//점=([0]/[2],[1]/[2])
	pint calY(int x){return {-a*x-c,b};}//val=[0]/[1]
};

ostream& operator<<(ostream& s,const Line& x){return s<<showpos<<x.a<<"x"<<x.b<<"y"<<x.c<<"=0";}

using i128=__int128;
ostream& operator<<(ostream& s,i128 a){
	if(!a){cout<<0;return s;}
	if(a<0)cout<<'-',a*=-1;
	i128 b=1;//rev of a
	while(a)
		b*=10,b+=a%10,a/=10;
	while(b!=1)
		cout<<signed(b%10),b/=10;
	return s;
}

#define FASTIO

//INPUT, strstream으로 더 깔끔하게 가능할까?
struct FastCIN{
	static const int SZ=1<<24;
	unsigned cnt=0;char a[SZ+1],*p;
	FastCIN(){preload();}
	void tie(int x){}
	int preload(){return cnt=cin.read(p=a,SZ).gcount();}
	inline char pop(){if(!cnt)preload(); return cnt>0?cnt--,*p++:0;}
	inline char get(){if(!cnt)preload(); return cnt>0?*p:0;}
	void ignore_wsc(){while(get()==' '||get()=='\n')pop();}
	operator bool(){return get();}
	template<class T>FastCIN& operator>>(T& n){ignore_wsc();n=0;char neg=false;if(get()=='-')neg=true,pop();while('0'<=get()&&get()<='9')n=n*10+pop()-'0';if(neg)n*=-1;return *this;}//int,i64,Mod<mod>
	FastCIN& operator>>(char& c){ignore_wsc();c=pop();return *this;}
	FastCIN& operator>>(string& s){ignore_wsc();s.clear();while(get()!=' '&&get()!='\n'&&get())s.pushb(pop());return *this;}
	FastCIN& operator>>(f64& n){ignore_wsc();string s;while(('0'<=get()&&get()<='9')||get()=='.'||get()=='-')s.pushb(pop());n=stod(s);return *this;}
	template<class T> FastCIN& operator>>(Arr<T>& a){for(auto& i:a)*this>>i;return *this;}
	template<class T,class U> FastCIN& operator>>(pair<T,U>& a){*this>>a.fi>>a.se;return *this;}
}fcin;
#define cin fcin

template<class... A> void _cinread(A&...a){((cin>>(a)),...);}
#define READ(T,...) T __VA_ARGS__;_cinread(__VA_ARGS__);

template<class T> ostream& operator<<(ostream& s,const Arr<T>& a){for(auto i:a)cout<<i<<' ';return s;}
template<class T> ostream& operator<<(ostream& o,const pair<T,T>& x){return o<<x.fi<<' '<<x.se;}
template<class... A> void PRINT(A...a){((cout<<a<<' '),...,(cout<<endl));}

//

//NOTE:골치아프면 걍 리차오 쓰자

bool fraclt(pint a,pint b){
	if(a.se<0)a.fi*=-1,a.se*=-1;
	if(b.se<0)b.fi*=-1,b.se*=-1;
	return a.fi*b.se<b.fi*a.se;
}

//max(lower convex envelope), increasing tangent
//3x3 determinant로 교점안구하고 cht가능
//https://www.geeksforgeeks.org/check-three-straight-lines-concurrent-not/
//point-line duality로 y=ax+b == (a,-b)형태 변환하고 ccw사용하는것도 가능
template<class T>
struct CHTint{
	Arr<pair<Line,T>> stk;
	i128 det(Line x,Line y,Line z){return (i128)x.a*y.b*z.c+(i128)x.b*y.c*z.a+(i128)x.c*y.a*z.b-(i128)x.c*y.b*z.a-(i128)x.b*y.a*z.c-(i128)x.a*y.c*z.b;}
	void push(Line a,T v){
		while(sz(stk)>=2 and det(stk[-2].fi,stk[-1].fi,a)>=0)
			stk.popb();
		if(sz(stk) and stk.back().fi.tan()==a.tan()){
			if(fraclt(stk.back().fi.calY(0),a.calY(0)))
				stk.back()={a,v};
			return;
		}
		stk.pushb(a,v);
	}
	int i=0;
	pair<pint,T> q(int x){
		while(i+1<sz(stk)){
			auto [a,b,c]=stk[i].fi.intersect(stk[i+1].fi);
			if(fraclt({x,1},{a,c}))break;
			i++;
		};
		return {stk[i].fi.calY(x),stk[i].se};
	}
};

auto mri(auto it) { return make_reverse_iterator(it); }  //*mri(it) == *prev(it)
auto rerase(auto& c, auto ri) { return mri(c.erase(prev(ri.base()))); }

using T=f64;
struct L{
	T tan, yic;
	mutable f64 lx = -1 / 0.0, rx = 1 / 0.0;

	bool operator<(const L& r) const { return tan < r.tan; }
	bool operator<(const T x) const { return rx < x; }

	f64 cpx(const L& r) const { return (r.yic - yic) / f64(tan - r.tan); }
	T f(T x) const { return tan * x + yic; }
};

// max(lower convex envelope), increasing tangent
// Note:
// 점화식형태 d[i] = min{j<i}(a[j]*b[i]+c[j])+e[i]
// b[i]를 x, a[j]를 기울기로 생각하면 그려진다.
// min, max, j<i, i<j<n 모두 식정리해주면 가능하다.
struct CHTStk {
	Arr<L> st;

	void add(T tan, T yic) {
		L z{tan, yic, 0};
		while(sz(st)) {
			z.lx = st.back().cpx(z);
			if(tan == st.back().tan || z.lx < st.back().lx) st.popb();
			else
				break;
		}
		st.pushb(z);
	}

	// T q(T x){
	// 	int s=0, e=sz(st);
	// 	while(e-s>1){
	// 		int m=(s+e)/2;
	// 		(x<st[m].lx?e:s)=m;
	// 	}
	// 	return st[s].tan*x + st[s].yic;
	// }
	//쿼리하는 x값도 단조증가하면 O(n) 가능
	int s = 0;
	T q(T x) {
		while(s < sz(st) and x >= st[s].lx) s++;
		return st[s - 1].tan * x + st[s - 1].yic;
	}
};

// max(lower convex envelope)
struct CHTSet {
	void add(T a, T b) {
		auto it = s.find({a, b});
		if(it != s.end()) b = max(b, it->yic), s.erase(it);

		L z = {a, b};
		auto r = s.upper_bound(z);
		while(r != s.end() && z.cpx(*r) >= r->rx) r = s.erase(r);
		auto l = mri(s.lower_bound(z));
		while(l != s.rend() && z.cpx(*l) <= l->lx) l = rerase(s, l);

		z.rx = r != s.end() ? z.cpx(*r) : 1 / 0.;
		z.lx = l != s.rend() ? z.cpx(*l) : -1 / 0.;
		if(z.lx > z.rx) return;
		s.insert(z);
		if(r != s.end()) r->lx = z.rx;
		if(l != s.rend()) l->rx = z.lx;
	}

	T q(T x) {
		auto it = s.lower_bound(x);
		return it->tan * x + it->yic;
	}
private:
	set<L, less<>> s;
};

//Don't use it at interactive
#define endl '\n'


void solve(){
	int n,k; cin>>n>>k;
	// auto dp=ARR(k+1,n+2,0.-inf<int>());
	// dp[-1][0]=0;
	// for(int x=0;x<k;x++){
	// 	LiChao<LL> z;
	// 	z.add({dp[x-1][0]+1,0.-0});
	// 	for(int y=1;y<=n;y++){
	// 		z.add({dp[x-1][y]+1,0.-y});
	// 		dp[x][y]=z.q(y)/y;
	// 	}
	// }
	// cout<<dp[k-1][n]<<endl;

	// f64 s=0,e=n;
	// while(e-s>1e-6){
	// 	f64 m=(s+e)/2;
	// 	//정확히 K번의 라운드 대신, 라운드당 람다(m)의 패널티를 부여해서 계산?
	// 	//m=0이면 n번의 라운드 진행
	// 	//m=1이면 1번의 라운드 진행
	// 	//현재인원x라 할때 (반드시 전부다) 이겨서 얻는 점수 최대화
	// 	//f(x) = max(y<x,f(y)+(x-y)/x-m) = max(y<x,(f(y)+1-m)x-y)/x
	// 	//역추적으로 라운드개수 구해서 k와 비교. cht역추적...
		

	// }

	//그냥 삼분탐색으로 최솟값구하면 답이 된다는듯?
	//최대화문제가 최소화 삼분탐색이 되는건 라그랑주듀얼 같은데 아직 몬가몬가...
	func(f64,f,f64 m){
		// LiChao<LL> z;
		// z.add({-m,0});
		// f64 val;
		// for(int i=1;i<=n;i++){
		// 	val=z.q(i)/i;
		// 	z.add({val+1-m,0.-i});
		// 	cout<<val<<endl;
		// }

		CHTStk cht;
		cht.add(-m,0);
		f64 val;
		for(int i=1;i<=n;i++){
			val=cht.q(i)/i;
			cht.add(val+1-m,-i);
		}
		return val+m*k;
	};
	f64 s=0,e=1;
	while(e-s>1e-10){
		f64 m1=(s*2+e)/3,m2=(s+e*2)/3;
		// cout<<m1<<' '<<f(m1)<<' '<<m2<<' '<<f(m2)<<endl;
		if(f(m1)>f(m2)) s=m1;
		else e=m2;
	}
	cout<<f((s+e)/2)+1<<endl;//의도치않게 1만큼 작게나오는데 머리아프다 그만 생각하자
}
signed main(){
	// int ti=0,t;cin>>t;
	// while(++ti<=t)
	// 	cout<<"Case #"<<ti<<": ",
		solve();
}

Compilation message

akvizna.cpp:67:6: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   67 |  Arr(auto its, auto ite):P(its,ite){}
      |      ^~~~
akvizna.cpp:67:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   67 |  Arr(auto its, auto ite):P(its,ite){}
      |                ^~~~
akvizna.cpp:85:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   85 | template<class... A> auto ARR(auto n,A&&... a)
      |                               ^~~~
akvizna.cpp:234:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  234 | auto mri(auto it) { return make_reverse_iterator(it); }  //*mri(it) == *prev(it)
      |          ^~~~
akvizna.cpp:235:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  235 | auto rerase(auto& c, auto ri) { return mri(c.erase(prev(ri.base()))); }
      |             ^~~~
akvizna.cpp:235:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  235 | auto rerase(auto& c, auto ri) { return mri(c.erase(prev(ri.base()))); }
      |                      ^~~~
akvizna.cpp: In static member function 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = long double; _Functor = solve()::<lambda(f64)>; _ArgTypes = {long double}]':
akvizna.cpp:362:16: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  362 |   return val+m*k;
      |                ^
akvizna.cpp:357:7: note: 'val' was declared here
  357 |   f64 val;
      |       ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1184 KB Output is correct
2 Correct 30 ms 780 KB Output is correct
3 Correct 20 ms 772 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 780 KB Output is correct
2 Correct 21 ms 780 KB Output is correct
3 Correct 19 ms 768 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 768 KB Output is correct
2 Correct 19 ms 752 KB Output is correct
3 Correct 20 ms 844 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1196 KB Output is correct
2 Correct 21 ms 776 KB Output is correct
3 Correct 19 ms 756 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 768 KB Output is correct
2 Correct 20 ms 1208 KB Output is correct
3 Correct 19 ms 760 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 744 KB Output is correct
2 Correct 23 ms 1100 KB Output is correct
3 Correct 21 ms 780 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 780 KB Output is correct
2 Correct 22 ms 844 KB Output is correct
3 Correct 21 ms 764 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 768 KB Output is correct
2 Correct 21 ms 772 KB Output is correct
3 Correct 20 ms 768 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 780 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 20 ms 772 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 931 ms 14576 KB Output is correct
2 Correct 961 ms 14736 KB Output is correct
3 Correct 874 ms 14404 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 980 ms 14736 KB Output is correct
2 Correct 898 ms 14836 KB Output is correct
3 Correct 917 ms 14788 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 893 ms 14700 KB Output is correct
2 Correct 937 ms 15180 KB Output is correct
3 Correct 915 ms 15096 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 907 ms 14768 KB Output is correct
2 Correct 911 ms 14896 KB Output is correct
3 Correct 904 ms 14656 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 897 ms 14620 KB Output is correct
2 Correct 1034 ms 14968 KB Output is correct
3 Correct 883 ms 14624 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 957 ms 14940 KB Output is correct
2 Correct 922 ms 14772 KB Output is correct
3 Correct 879 ms 14528 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 981 ms 14952 KB Output is correct
2 Correct 912 ms 14528 KB Output is correct
3 Correct 943 ms 14528 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 922 ms 14656 KB Output is correct
2 Correct 919 ms 14976 KB Output is correct
3 Correct 858 ms 14544 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 952 ms 14828 KB Output is correct
2 Correct 934 ms 14812 KB Output is correct
3 Correct 1052 ms 14980 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 914 ms 14968 KB Output is correct
2 Correct 895 ms 14580 KB Output is correct
3 Correct 949 ms 15204 KB Output is correct

Subtask #24
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 945 ms 14956 KB Output is correct
2 Correct 943 ms 14920 KB Output is correct
3 Correct 946 ms 14884 KB Output is correct

Subtask #25
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 911 ms 15032 KB Output is correct
2 Correct 907 ms 15028 KB Output is correct
3 Correct 953 ms 15008 KB Output is correct

Subtask #26
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 927 ms 14968 KB Output is correct
2 Correct 902 ms 14952 KB Output is correct
3 Correct 962 ms 15192 KB Output is correct