oj.uz

Submission #1041306

# Submission time Handle Problem Language Result Execution time Memory
1041306 2024-08-01T20:48:47 Z Unforgettablepl Growing Vegetables is Fun 5 (JOI24_vegetables5) C++17
37 / 100
 3048 ms 35304 KB 
    #include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e13;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> arr(2*n+1);
	for(int i=1;i<=2*n;i++){
		cin>>arr[i];
	}
	vector<int> B(n);
	for(int&i:B)cin>>i;
	sort(B.begin(),B.end());
	vector<int> C(n);
	for(int&i:C)cin>>i;
	sort(C.begin(),C.end());
	auto check_support = [&](int x){
		// return a vector of bool of 1..n signifying if it works or not
		// check array against B
		vector<int> rarr(2*n+1);
		for(int i=1;i<=2*n;i++)rarr[2*n-i+1]=arr[i];
		vector<int> works(n+2);
		for(int i=1;i<=n;i++){
			auto it1 = lower_bound(B.begin(),B.end(),arr[i]-x);
			auto it2 = upper_bound(B.begin(),B.end(),arr[i]+x);
			if(it1==it2)continue;
			auto en = it1-B.begin();
			auto st = it2-B.begin()-1;
			int breakpoint = lower_bound(rarr.begin()+1,rarr.begin()+1+n,arr[i])-rarr.begin();
			breakpoint = n+2-breakpoint;
			st = max(i-st,1ll);
			en = max(min(i-en,i),0ll);
			if(breakpoint<st)continue;
			if(st<=breakpoint and breakpoint<=en)en = i;
			works[st]++;
			works[en+1]--;
		}
		for(int i=n+1;i<2*n;i++){
			auto it1 = lower_bound(B.begin(),B.end(),arr[i]-x);
			auto it2 = upper_bound(B.begin(),B.end(),arr[i]+x);
			if(it1==it2)continue;
			auto st = it1-B.begin();
			auto en = it2-B.begin()-1;
			int breakpoint = upper_bound(arr.begin()+1,arr.begin()+n,arr[i])-arr.begin();
			st = max(min(i+st-n,n+1),i-n+1);
			en = max(min(i+en-n,n),i-n);
			if(en<breakpoint)continue;
			if(st<=breakpoint and breakpoint<=en)st = i-n+1;
			works[st]++;  
			works[en+1]--;
		}
		for(int i=1;i<=n;i++)works[i]+=works[i-1];
		vector<bool> res(n+1);
		for(int i=1;i<=n;i++)res[i]=works[i]==n;
		return res;
	};
	auto actcheck = [&](int x){
		auto t1 = check_support(x);
		swap(B,C);
		vector<int> newarr(2*n+1);
		for(int i=1;i<=n;i++)newarr[i+n]=arr[i];
		for(int i=n+1;i<=2*n;i++)newarr[i-n]=arr[i];
		for(int&i:B)i*=-1;
		for(int&i:newarr)i*=-1;
		reverse(B.begin(),B.end());
		swap(newarr,arr);
		auto t2 = check_support(x);
		swap(newarr,arr);
		reverse(B.begin(),B.end());
		for(int&i:B)i*=-1;
		swap(B,C);
		for(int i=1;i<=n;i++)if(t1[i] and t2[i])return true;
		return false;
	};
	auto check = [&](int x){
		if(actcheck(x))return true;
		swap(B,C);
		if(actcheck(x))return true;
		return false;
	};
	check(0);
	int ans = 0;
	for(int jump=536870912;jump;jump/=2){
		if(!check(jump+ans-1))ans+=jump;
	}
	cout << ans << '\n';
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 21.0

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

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 33376 KB Output is correct
2 Correct 2808 ms 29728 KB Output is correct
3 Correct 2110 ms 24772 KB Output is correct
4 Correct 2437 ms 33244 KB Output is correct
5 Correct 2368 ms 29876 KB Output is correct
6 Correct 65 ms 1380 KB Output is correct
7 Correct 2753 ms 33896 KB Output is correct
8 Correct 2650 ms 28652 KB Output is correct
9 Correct 2041 ms 33240 KB Output is correct
10 Correct 2637 ms 33228 KB Output is correct
11 Correct 2671 ms 35304 KB Output is correct
12 Correct 2635 ms 30920 KB Output is correct
13 Correct 2779 ms 29752 KB Output is correct
14 Correct 2547 ms 33248 KB Output is correct
15 Correct 2159 ms 29716 KB Output is correct
16 Correct 2396 ms 29792 KB Output is correct

Subtask #5
0 / 33.0

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