oj.uz

답안 #282603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282603 2020-08-24T15:30:37 Z cgiosy Akvizna (COCI19_akvizna) C++17
130 / 130
 1329 ms 2608 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using flt=double;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K;
	flt l=0, r=1+1e-12;
	vector<int> C(N+1), P(N+1);
	cout<<fixed<<setprecision(9);
	auto f=[&](flt m) {
		vector<double> D(N+1);
		vector<int> T(1<<32-__builtin_clz(N));
		auto f=[&](int j, int i) {
			return D[j]+flt(i-j)/i;
		};
		auto cmp=[&](int i, int j, int x) {
			return f(i, x)>f(j, x);
		};
		auto add=[&](int a) {
			int s=1, e=N, i=1;
			while(i) {
				int m=s+e>>1, &b=T[i];
				if(cmp(a, b, m)) swap(a, b);
				if(cmp(a, b, s)) e=m-1, i=i*2;
				else if(cmp(a, b, e)) s=m+1, i=i*2+1;
				else break;
			}
		};
		auto get=[&](int x) {
			int s=1, e=N, i=1, a=0;
			while(i) {
				int m=s+e>>1, b=T[i];
				if(cmp(b, a, x)) a=b;
				if(x<m) e=m-1, i=i*2;
				else if(x>m) s=m+1, i=i*2+1;
				else break;
			}
			return a;
		};
		D[0]=0;
		for(int i=1; i<=N; i++) {
			add(i-1);
			int p=get(i);
			P[i]=p;
			C[i]=C[p]+1;
			D[i]=f(p, i)-m;
		}
		return make_pair(C[N], D[N]+K*m);
	};
	while(r-l>1e-12) {
		flt m=(l+r)/2;
		auto[k,x]=f(m);
		if(k<K) r=m;
		else if(k>K) l=m;
		else { l=r=m; break; }
	}
	cout<<fixed<<setprecision(9)<<f((l+r)/2).second;
}

Compilation message

akvizna.cpp: In lambda function:
akvizna.cpp:15:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |   vector<int> T(1<<32-__builtin_clz(N));
      |                    ~~^~~~~~~~~~~~~~~~~
akvizna.cpp: In lambda function:
akvizna.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int m=s+e>>1, &b=T[i];
      |           ~^~
akvizna.cpp: In lambda function:
akvizna.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=s+e>>1, b=T[i];
      |           ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 23 ms 440 KB Output is correct
3 Correct 20 ms 384 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 512 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 436 KB Output is correct
2 Correct 20 ms 436 KB Output is correct
3 Correct 21 ms 384 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1117 ms 2452 KB Output is correct
2 Correct 1222 ms 2396 KB Output is correct
3 Correct 1158 ms 2352 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1132 ms 2376 KB Output is correct
2 Correct 1243 ms 2556 KB Output is correct
3 Correct 1222 ms 2432 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 2436 KB Output is correct
2 Correct 1285 ms 2532 KB Output is correct
3 Correct 1259 ms 2540 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1188 ms 2408 KB Output is correct
2 Correct 1255 ms 2552 KB Output is correct
3 Correct 1215 ms 2372 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1068 ms 2336 KB Output is correct
2 Correct 1268 ms 2432 KB Output is correct
3 Correct 1198 ms 2448 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1282 ms 2608 KB Output is correct
2 Correct 1225 ms 2440 KB Output is correct
3 Correct 1209 ms 2452 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1186 ms 2432 KB Output is correct
2 Correct 1180 ms 2352 KB Output is correct
3 Correct 1184 ms 2344 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1071 ms 2376 KB Output is correct
2 Correct 1329 ms 2464 KB Output is correct
3 Correct 1182 ms 2468 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1143 ms 2540 KB Output is correct
2 Correct 1252 ms 2432 KB Output is correct
3 Correct 1278 ms 2432 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1166 ms 2540 KB Output is correct
2 Correct 1233 ms 2444 KB Output is correct
3 Correct 1279 ms 2432 KB Output is correct

Subtask #24
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1174 ms 2532 KB Output is correct
2 Correct 1292 ms 2472 KB Output is correct
3 Correct 1289 ms 2528 KB Output is correct

Subtask #25
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1074 ms 2532 KB Output is correct
2 Correct 1296 ms 2532 KB Output is correct
3 Correct 1289 ms 2528 KB Output is correct

Subtask #26
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1241 ms 2536 KB Output is correct
2 Correct 1275 ms 2528 KB Output is correct
3 Correct 1303 ms 2476 KB Output is correct