Submission #23500173

Source Code Expand

#include<bits/stdc++.h>

#define ll long long 

using namespace std;

int read()
{
	int a=0,f=1,c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		a=a*10+c-'0';
		c=getchar();
	}
	return a*f;
}

const int K=1e5+10;

int k;
int n,m;
ll a[K],L[K],R[K];

bool check(ll d)
{
	ll sl=0,sr=0;
	for(int i=1;i<=k;++i)
	{
		L[i]=(max(a[i]*m-d,(ll)0)+n-1)/n;sl+=L[i];
		R[i]=(a[i]*m+d)/n;sr+=R[i];
	}
	
	if(sl<=m && m<=sr)
	{
		ll ext=m-sl;
		for(int i=1;i<=k;++i)
		{
			ll t=min(ext,(ll)R[i]-L[i]);
			L[i]+=t;ext-=t;
		}
		return 1;
	}
	else return 0;
}

int main()
{
//	freopen("1.in","r",stdin);
	
	k=read();
	n=read();m=read();
	for(int i=1;i<=k;++i)a[i]=read();
	
	ll l=0,r=1e18;
	while(l<r)
	{
		ll mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	
	check(l);
	for(int i=1;i<=k;++i)printf("%lld ",L[i]);
	puts("");
	
	return 0;
}

Submission Info

Submission Time
Task B - Village of M People
User WhereIsDodoco
Language C++ (GCC 9.2.1)
Score 400
Code Size 949 Byte
Status AC
Exec Time 121 ms
Memory 6092 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 60
Set Name Test Cases
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 01_sample_04.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 01_sample_04.txt, 02_rand_01.txt, 02_rand_02.txt, 02_rand_03.txt, 02_rand_04.txt, 02_rand_05.txt, 02_rand_06.txt, 02_rand_07.txt, 02_rand_08.txt, 02_rand_09.txt, 02_rand_10.txt, 02_rand_11.txt, 02_rand_12.txt, 02_rand_13.txt, 02_rand_14.txt, 02_rand_15.txt, 02_rand_16.txt, 02_rand_17.txt, 02_rand_18.txt, 02_rand_19.txt, 02_rand_20.txt, 03_small_N_01.txt, 03_small_N_02.txt, 03_small_N_03.txt, 03_small_N_04.txt, 03_small_N_05.txt, 03_small_N_06.txt, 03_small_N_07.txt, 03_small_N_08.txt, 03_small_N_09.txt, 03_small_N_10.txt, 04_small_M_01.txt, 04_small_M_02.txt, 04_small_M_03.txt, 04_small_M_04.txt, 04_small_M_05.txt, 04_small_M_06.txt, 04_small_M_07.txt, 04_small_M_08.txt, 04_small_M_09.txt, 04_small_M_10.txt, 05_small_NM_01.txt, 05_small_NM_02.txt, 05_small_NM_03.txt, 05_small_NM_04.txt, 05_small_NM_05.txt, 05_small_NM_06.txt, 05_small_NM_07.txt, 05_small_NM_08.txt, 05_small_NM_09.txt, 05_small_NM_10.txt, 06_numerical_error_01.txt, 06_numerical_error_02.txt, 06_numerical_error_03.txt, 06_numerical_error_04.txt, 06_numerical_error_05.txt, 07_handmade_01.txt
Case Name Status Exec Time Memory
01_sample_01.txt AC 5 ms 3588 KiB
01_sample_02.txt AC 2 ms 3712 KiB
01_sample_03.txt AC 2 ms 3708 KiB
01_sample_04.txt AC 3 ms 3600 KiB
02_rand_01.txt AC 98 ms 5432 KiB
02_rand_02.txt AC 75 ms 4872 KiB
02_rand_03.txt AC 104 ms 5632 KiB
02_rand_04.txt AC 110 ms 5816 KiB
02_rand_05.txt AC 42 ms 4212 KiB
02_rand_06.txt AC 42 ms 4360 KiB
02_rand_07.txt AC 75 ms 4924 KiB
02_rand_08.txt AC 61 ms 4692 KiB
02_rand_09.txt AC 91 ms 5464 KiB
02_rand_10.txt AC 85 ms 5176 KiB
02_rand_11.txt AC 108 ms 5756 KiB
02_rand_12.txt AC 11 ms 3712 KiB
02_rand_13.txt AC 75 ms 5020 KiB
02_rand_14.txt AC 116 ms 5896 KiB
02_rand_15.txt AC 36 ms 4108 KiB
02_rand_16.txt AC 45 ms 4172 KiB
02_rand_17.txt AC 13 ms 3772 KiB
02_rand_18.txt AC 48 ms 4452 KiB
02_rand_19.txt AC 54 ms 4300 KiB
02_rand_20.txt AC 33 ms 4068 KiB
03_small_N_01.txt AC 104 ms 5680 KiB
03_small_N_02.txt AC 56 ms 4624 KiB
03_small_N_03.txt AC 60 ms 4580 KiB
03_small_N_04.txt AC 58 ms 4740 KiB
03_small_N_05.txt AC 99 ms 5404 KiB
03_small_N_06.txt AC 108 ms 5704 KiB
03_small_N_07.txt AC 60 ms 4744 KiB
03_small_N_08.txt AC 107 ms 5772 KiB
03_small_N_09.txt AC 110 ms 5856 KiB
03_small_N_10.txt AC 56 ms 4440 KiB
04_small_M_01.txt AC 60 ms 4572 KiB
04_small_M_02.txt AC 51 ms 4500 KiB
04_small_M_03.txt AC 27 ms 3916 KiB
04_small_M_04.txt AC 80 ms 5208 KiB
04_small_M_05.txt AC 28 ms 3740 KiB
04_small_M_06.txt AC 17 ms 3744 KiB
04_small_M_07.txt AC 88 ms 5248 KiB
04_small_M_08.txt AC 121 ms 6088 KiB
04_small_M_09.txt AC 10 ms 3712 KiB
04_small_M_10.txt AC 43 ms 4212 KiB
05_small_NM_01.txt AC 76 ms 4988 KiB
05_small_NM_02.txt AC 33 ms 4036 KiB
05_small_NM_03.txt AC 86 ms 5220 KiB
05_small_NM_04.txt AC 20 ms 3832 KiB
05_small_NM_05.txt AC 51 ms 4604 KiB
05_small_NM_06.txt AC 85 ms 5128 KiB
05_small_NM_07.txt AC 121 ms 6092 KiB
05_small_NM_08.txt AC 110 ms 5796 KiB
05_small_NM_09.txt AC 21 ms 4000 KiB
05_small_NM_10.txt AC 15 ms 3764 KiB
06_numerical_error_01.txt AC 67 ms 4896 KiB
06_numerical_error_02.txt AC 7 ms 3648 KiB
06_numerical_error_03.txt AC 52 ms 4620 KiB
06_numerical_error_04.txt AC 75 ms 4924 KiB
06_numerical_error_05.txt AC 53 ms 4620 KiB
07_handmade_01.txt AC 2 ms 3580 KiB