oj.uz

Submission #554695

# Submission time Handle Problem Language Result Execution time Memory
554695 2022-04-29T07:53:05 Z new_acc Cipele (COCI18_cipele) C++14
90 / 90
 40 ms 2896 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod=998244353;
const ll mod2=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t1[N],t2[N];
int n,m;
bool check(int x){
	int wsk=m;
	for(int i=n;i>=1;i--){
		while(wsk>0 and abs(t1[i]-t2[wsk])>x) wsk--;
		if(wsk==0) return 0;
		wsk--;
	}
	return 1;
}
int bs(int pocz,int kon){
	int res=0;
	while(pocz<=kon){
		int sr=(pocz+kon)>>1;
		if(check(sr)) res=sr,kon=sr-1;
		else pocz=sr+1;
	}
	return res;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>t1[i];
	for(int i=1;i<=m;i++) cin>>t2[i];
	sort(t1+1,t1+1+n),sort(t2+1,t2+1+m);
	if(m<n){
		for(int i=1;i<=max(n,m);i++) swap(t1[i],t2[i]);
		swap(n,m);
	}
	cout<<bs(0,1e9)<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2620 KB Output is correct
2 Correct 37 ms 2844 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2896 KB Output is correct
2 Correct 40 ms 2892 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 432 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2364 KB Output is correct
2 Correct 20 ms 1748 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2508 KB Output is correct
2 Correct 17 ms 2116 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2292 KB Output is correct
2 Correct 33 ms 2492 KB Output is correct