Submission #1248648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248648		Bui_Quoc_Cuong	Room Temperature (JOI24_ho_t1)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
const int N = 5e5 + 5;
int n,k;
int a[N];
void init()
{
	cin>>n>>k;
	FOR(i,1,n) cin>>a[i];
}
namespace sub1
{

	void solve()
	{
		int ans=2e9;
		FOR(t,1,50000)
		{
			int ma=0;
			FOR(i,1,n)
			{
				if(a[i]>=t)
				{	
					int tam=(a[i]-t)/k;
					int val=a[i] -k*tam;
					int curma = abs(t-val);

					tam++;
					val=a[i]-k*tam;
					curma=min(curma,abs(val-t));

					tam--; tam--;
					curma=min(curma,abs(val-t));

					ma=max(ma,curma);
				} else ma=max(ma,abs(t-a[i]));
			}	
			ans=min(ans,ma);
		}
		cout << ans;
	}
}
namespace sub2
{
	int tinh(int x, int y)
	{
		int l = 0, r = (y - x) / k + 20, res = 0;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if (x - mid * k >= y) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		int cost1 = abs((x - res * k) - y);
		int cost2 = abs((x - (res + 1) * k) - y);
		int cost3 = abs((x - (res - 1) * k) - y);
		return min({cost1,cost2,cost3});
	}
	int calc(int t)
	{
		int ma=0;
		FOR(i,1,n)
		{
			if(a[i]>t)
			{	
				ma=max(ma,tinh(a[i],t));
			} else ma=max(ma,abs(t-a[i]));
		}	
		return ma;
	}
	void solve()
	{
		int l=0,r=1e9,ans=2e9;
		FOR(time,1,50)
		{
			int mid1 = l + (r-l)/3;
			int mid2 = r - (r-l)/3;

			int cost1 = calc(mid1);
			int cost2 = calc(mid2);

			ans=min(ans,cost1); ans=min(ans,cost2);

			if(cost1 <= cost2)
			{
				r=mid2;
			} else l=mid1;
		}
		cout << ans;
	}
}
void process()
{
	// sub1::solve();
	sub2::solve();
}
signed main(void) 
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);   
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")) 
    { 
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 15