oj.uz

Submission #263231

# Submission time Handle Problem Language Result Execution time Memory
263231 2020-08-13T14:19:54 Z amiratou Pyramid Base (IOI08_pyramid_base) C++14
20 / 100
 5000 ms 10460 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;
		int a,b,c,d;
		for (int i = 0; i < p; ++i)
		{
			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-1;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			a=tab[i].x2+1;
			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].y2+1;
			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;}
			//cerr<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";
			//sep();

			c=tab[i].x1-1;
			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;}
		}
		for (int i = 1; i <= n; ++i)
		{
			a=i,b=1;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=i,d=m;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}
		}
		for (int i = 1; i <= m; ++i)
		{
			a=1,b=i;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=n,d=i;
			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

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 989 ms 384 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 384 KB Output is correct
2 Execution timed out 5095 ms 384 KB Time limit exceeded

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1345 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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