oj.uz

답안 #263085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263085 2020-08-13T12:52:39 Z amiratou Pyramid Base (IOI08_pyramid_base) C++14
10 / 100
 5000 ms 8184 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
struct obs
{
	int x1,y1,x2,y2,cost;
};
obs tab[400001];
int n,m,B,p;
bool inter(int idx,int X1,int Y1,int X2,int Y2){
	if(X1<=0 || Y1<=0 || X2>n || Y2>m)return 1;
	for (int i = 0; i < p; ++i)
	{
		if(i==idx)continue;
		if(Y1>=tab[i].y2 || Y2<=tab[i].y1)
			continue;
		if(X1>=tab[i].x2 || X2<=tab[i].x1)
			continue;
		return 1;
	}
	return 0;
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>m>>B>>p;
	for (int i = 0; i < p; ++i)
		cin>>tab[i].x1>>tab[i].y1>>tab[i].x2>>tab[i].y2>>tab[i].cost;
	int l=0,r=min(n,m),ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		bool f=0;
		for (int i = 0; i < p; ++i)
		{
			int a,b,c,d;
			a=tab[i].x1;
			b=tab[i].y1-med;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2;
			d=tab[i].y1;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			a=tab[i].x2;
			b=tab[i].y1;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2+med;
			d=tab[i].y2;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			a=tab[i].x1;
			b=tab[i].y1+med;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2;
			d=tab[i].y2+med;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			c=tab[i].x1;
			d=tab[i].y2;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x1;
			d=tab[i].y1+med;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}
		}
		if(f)l=med+1,ans=med;
		else r=med-1;
	}
	assert(ans!=-1);
	cout<<ans<<"\n";
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 384 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 384 KB Output isn't correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 384 KB Output isn't correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 804 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5062 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5098 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5095 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5090 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5092 ms 4216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5074 ms 6264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5098 ms 8184 KB Time limit exceeded
2 Halted 0 ms 0 KB -