結果

問題 No.67 よくある棒を切る問題 (1)
コンテスト
ユーザー anta
提出日時 2015-09-04 19:25:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,121 bytes
コンパイル時間 533 ms
コンパイル使用メモリ 77,448 KB
最終ジャッジ日時 2025-03-03 10:23:12
合計ジャッジ時間 1,157 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:150:75: error: ‘uintptr_t’ does not name a type
  150 |                 double *A_d = reinterpret_cast<double*>((reinterpret_cast<uintptr_t>(A_d_buf) | 31) + 1);
      |                                                                           ^~~~~~~~~
main.cpp:18:1: note: ‘uintptr_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
   17 | #include <functional>
  +++ |+#include <cstdint>
   18 | 
main.cpp:148:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |         {       scanf("%d", &N);
      |                 ~~~~~^~~~~~~~~~
main.cpp:153:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  153 |                         scanf("%d", &A);
      |                         ~~~~~^~~~~~~~~~
main.cpp:157:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  157 |                 scanf("%lld", &K);
      |                 ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0