oj.uz

Submission #240207

# Submission time Handle Problem Language Result Execution time Memory
240207 2020-06-18T18:25:08 Z hzhuarry Cipele (COCI18_cipele) C++17
90 / 90
 56 ms 1532 KB 
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

#define endl "\n"
#define pf push_front
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define f first
#define s second
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PI 3.14159265358979323846264338327950L
#define lb lower_bound
#define ub upper_bound


typedef long long ll;
typedef long double ld;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<ld> vd;
typedef vector<str> vs;

typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpd;

const int MOD = 1000000007;
const int dx[4]= {-1,1,0,0}, dy[4]= {0,0,-1,1}; //flood

int N,M;
vi l,r;

bool ok(int ugly)
{
    int cnt=0,j=0;
    for(int i=0;i<N&&j<M;++i)
    {
        int curr=l[i];
        while(j<M&&abs(r[j]-curr)>ugly)++j;
        if(j>=M)break;
        cnt++;
        ++j;
    }
    return cnt>=N;
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //ifstream cin (".in");
    //ofstream cout (".out");
    
    cin>>N>>M;
    for(int i=0;i<N;++i){
        int a;
        cin>>a;
        l.pb(a);
    }
    for(int i=0;i<M;++i)
    {
        int b;
        cin>>b;
        r.pb(b);
    }
    if(N>M)
    {
        swap(l,r);
        swap(N, M);
    }
    SORT(l);
    SORT(r);
    int lo=0,hi=1e9;
    while(lo<hi)
    {
        int mid=(lo+hi)/2;
        if(ok(mid)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    cout<<lo<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1532 KB Output is correct
2 Correct 52 ms 1524 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1524 KB Output is correct
2 Correct 56 ms 1532 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1404 KB Output is correct
2 Correct 33 ms 1024 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1404 KB Output is correct
2 Correct 30 ms 1148 KB Output is correct

Subtask #10
9.0 / 9.0

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