oj.uz

Submission #352419

# Submission time Handle Problem Language Result Execution time Memory
352419 2021-01-20T18:15:07 Z arnold518 Kosta (COI14_kosta) C++14
48 / 100
 5000 ms 1900 KB 
#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[i].x-A[j].x, A[j].y-A[i].y, A[i].y-A[j].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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1260 KB Output is correct
2 Correct 28 ms 1260 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1900 KB Output is correct
2 Correct 46 ms 1900 KB Output is correct

Subtask #5
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #6
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2656 ms 400 KB Output is correct
2 Correct 2483 ms 440 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 492 KB Output is correct
2 Correct 1597 ms 444 KB Output is correct

Subtask #9
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5087 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -