#47336 (C++11) No.67 よくある棒を切る問題 (1)

提出ソース

結果

問題	No.67 よくある棒を切る問題 (1)
ユーザー	anta
提出日時	2015-09-04 19:25:42
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	32 ms / 5,000 ms
コード長	4,121 bytes
コンパイル時間	630 ms
コンパイル使用メモリ	74,672 KB
実行使用メモリ	4,892 KB
最終ジャッジ日時	2023-08-08 05:56:49
合計ジャッジ時間	2,713 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	32 ms 4,576 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	12 ms 4,380 KB
testcase_03	AC	23 ms 4,376 KB
testcase_04	AC	29 ms 4,664 KB
testcase_05	AC	29 ms 4,612 KB
testcase_06	AC	28 ms 4,712 KB
testcase_07	AC	32 ms 4,620 KB
testcase_08	AC	32 ms 4,880 KB
testcase_09	AC	31 ms 4,732 KB
testcase_10	AC	26 ms 4,484 KB
testcase_11	AC	28 ms 4,612 KB
testcase_12	AC	25 ms 4,480 KB
testcase_13	AC	29 ms 4,380 KB
testcase_14	AC	30 ms 4,568 KB
testcase_15	AC	27 ms 4,456 KB
testcase_16	AC	28 ms 4,672 KB
testcase_17	AC	28 ms 4,664 KB
testcase_18	AC	27 ms 4,664 KB
testcase_19	AC	30 ms 4,680 KB
testcase_20	AC	30 ms 4,892 KB
testcase_21	AC	30 ms 4,660 KB
testcase_22	AC	25 ms 4,380 KB
testcase_23	AC	26 ms 4,640 KB
testcase_24	AC	1 ms 4,380 KB
testcase_25	AC	2 ms 4,380 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	6 ms 4,380 KB
testcase_29	AC	4 ms 4,380 KB
testcase_30	AC	2 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>

#ifdef MY_LOCAL_RUN
#include <immintrin.h>
#endif

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

extern "C" long long sum_trunc_mul(double *A, int N, double s_inv);

#ifdef MY_LOCAL_RUN
__attribute__((noinline)) long long sum_trunc_mul(double *A, int N, double s_inv) {
	__m256d inv = _mm256_set1_pd(s_inv);
	int i = 0;
	__m256d sum = _mm256_setzero_pd();
	for(; i + 3 < N; i += 4) {
		__m256d a_d = _mm256_load_pd(A + i);
		__m256d prod = _mm256_mul_pd(a_d, inv);
		__m256d truncated = _mm256_round_pd(prod, (_MM_FROUND_TO_ZERO |_MM_FROUND_NO_EXC));
		sum = _mm256_add_pd(sum, truncated);
	}
	double sum4[4];
	_mm256_storeu_pd(sum4, sum);
	long long res = 0;
	rep(k, 4) res += (ll)sum4[k];
	for(; i < N; ++ i)
		res += (ll)(A[i] * s_inv);
	return res;
}
#else
__asm(
"	.text\n"
"	.p2align 4,,15\n"
"	.globl	sum_trunc_mul\n"
"	.type	sum_trunc_mul, @function\n"
"sum_trunc_mul:\n"
".L_FB4609:\n"
"	.cfi_startproc\n"
"	pushq	%rbp\n"
"	.cfi_def_cfa_offset 16\n"
"	.cfi_offset 6, -16\n"
"	vmovddup	%xmm0, %xmm3\n"
"	vinsertf128	$1, %xmm3, %ymm3, %ymm3\n"
"	movq	%rsp, %rbp\n"
"	.cfi_def_cfa_register 6\n"
"	andq	$-32, %rsp\n"
"	addq	$16, %rsp\n"
"	cmpl	$3, %esi\n"
"	jle	.L_9\n"
"	leal	-4(%rsi), %ecx\n"
"	movq	%rdi, %rax\n"
"	vxorpd	%xmm1, %xmm1, %xmm1\n"
"	shrl	$2, %ecx\n"
"	movl	%ecx, %edx\n"
"	salq	$5, %rdx\n"
"	leaq	32(%rdi,%rdx), %rdx\n"
"	.p2align 4,,10\n"
"	.p2align 3\n"
".L_4:\n"
"	vmulpd	(%rax), %ymm3, %ymm2\n"
"	addq	$32, %rax\n"
"	vroundpd	$11, %ymm2, %ymm2\n"
"	cmpq	%rdx, %rax\n"
"	vaddpd	%ymm2, %ymm1, %ymm1\n"
"	jne	.L_4\n"
"	leal	4(,%rcx,4), %r9d\n"
".L_2:\n"
"	vmovupd	%ymm1, -48(%rsp)\n"
"	leaq	-48(%rsp), %rdx\n"
"	xorl	%eax, %eax\n"
"	leaq	-16(%rsp), %r8\n"
".L_6:\n"
"	vmovsd	(%rdx), %xmm1\n"
"	addq	$8, %rdx\n"
"	vcvttsd2siq	%xmm1, %rcx\n"
"	addq	%rcx, %rax\n"
"	cmpq	%r8, %rdx\n"
"	jne	.L_6\n"
"	cmpl	%r9d, %esi\n"
"	jle	.L_10\n"
"	subl	$1, %esi\n"
"	movslq	%r9d, %rcx\n"
"	leaq	(%rdi,%rcx,8), %rdx\n"
"	subl	%r9d, %esi\n"
"	addq	%rsi, %rcx\n"
"	leaq	8(%rdi,%rcx,8), %rsi\n"
"	.p2align 4,,10\n"
"	.p2align 3\n"
".L_8:\n"
"	vmulsd	(%rdx), %xmm0, %xmm1\n"
"	addq	$8, %rdx\n"
"	vcvttsd2siq	%xmm1, %rcx\n"
"	addq	%rcx, %rax\n"
"	cmpq	%rsi, %rdx\n"
"	jne	.L_8\n"
".L_10:\n"
"	vzeroupper\n"
"	leave\n"
"	.cfi_remember_state\n"
"	.cfi_def_cfa 7, 8\n"
"	ret\n"
".L_9:\n"
"	.cfi_restore_state\n"
"	vxorpd	%xmm1, %xmm1, %xmm1\n"
"	xorl	%r9d, %r9d\n"
"	jmp	.L_2\n"
"	.cfi_endproc\n"
"\n");

#endif

int main() {
	int N;
	{	scanf("%d", &N);
		char *A_d_buf = new char[N * 8 + 32];
		double *A_d = reinterpret_cast<double*>((reinterpret_cast<uintptr_t>(A_d_buf) | 31) + 1);
		rep(i, N) {
			int A;
			scanf("%d", &A);
			A_d[i] = A;
		}
		long long K;
		scanf("%lld", &K);
		const double EPS = 1e-9;
		double l = 0, u = 1e9;
		while(l + EPS < u && l * (1 + EPS) < u) {
			double mid = (l + u) / 2;
			double inv = 1. / mid;
			long long sum = sum_trunc_mul(A_d, N, inv);
			if(sum >= K) l = mid; else u = mid;
		}
		printf("%.10f\n", (l + u) / 2);
		delete[] A_d_buf;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード