Submission #352416

#	Time	Username	Problem	Language	Result	Execution time	Memory
352416		arnold518	Kosta (COI14_kosta)	C++14	20 / 100	5093 ms	2028 KiB

kosta

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define x first
#define y second

const int MAXN = 2e5;
const int INF = 2e8;

int N, K;
pii A[MAXN+10];

int D;
int ans1, ans2;

bool solve(int _D)
{
	D=_D;

	for(int j=1; j<=N; j++)
	{
		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=1; i<=N; i++)
		{
			if(max({A[j].x-A[i].x, A[j].x+A[i].x, A[j].y-A[i].y, A[j].y+A[i].y})<=D) continue;
			xl=min(xl, A[i].x);
			xr=max(xr, A[i].x);
			yl=min(yl, A[i].y);
			yr=max(yr, A[i].y);
		}
		if(xl==INF)
		{
			ans1=ans2=j;
			return true;
		}
		for(int i=1; i<=N; i++)
		{
			int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
			if(t<=D)
			{
				ans1=j; ans2=i;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &K, &N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].x, &A[i].y);
		int x2=A[i].x+A[i].y;
		int y2=A[i].x-A[i].y;
		A[i]={x2, y2};
	}

	if(K==1)
	{
		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=1; i<=N; i++)
		{
			xl=min(xl, A[i].x);
			xr=max(xr, A[i].x);
			yl=min(yl, A[i].y);
			yr=max(yr, A[i].y);
		}
		int D=INF, ans=-1;
		for(int i=1; i<=N; i++)
		{
			int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
			if(D>=t) D=t, ans=i;
		}
		printf("%d\n%d\n", D, ans);
	}
	else
	{
		int lo=0, hi=INF;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(solve(mid)) hi=mid;
			else lo=mid;
		}
		solve(hi);
		printf("%d\n%d %d\n", hi, ans1, ans2);
	}
}

Compilation message (stderr)

kosta.cpp: In function 'int main()':
kosta.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |    int mid=lo+hi>>1;
      |            ~~^~~
kosta.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d%d", &K, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~
kosta.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d%d", &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 0 / 2
• Subtask 6: 0 / 2
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 26
• Subtask 10: 0 / 26