oj.uz

Submission #1039947

# Submission time Handle Problem Language Result Execution time Memory
1039947 2024-07-31T12:55:40 Z 7again Cipele (COCI18_cipele) C++17
90 / 90
 70 ms 8480 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define FAST ios::sync_with_stdio(0);cout.tie(0);cin.tie(0)
//#define endl "\n"
#define f first
#define s second
#define pb push_back
#define in insert

//#define ind(v,t) distance(v.begin(),t)
using namespace std ;

int MOD = 1e18 ;
const int N = 200000 ;

//int fib(int n){double phi=(1+sqrt(5))/2;return round((pow(phi,n)-pow(1-phi,n))/sqrt(5));}
//void setIO(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
int fstpow(int a, int b){if(b==0)return 1;int ans=fstpow(a,b/2)%MOD;ans=ans%MOD*ans%MOD;if(b&1)return a*ans%MOD;return ans%MOD;}
int inv(int x){return fstpow(x,MOD-2);}
int DMOD(int x,int y){x%=MOD;y%=MOD;return fstpow(x,inv(y));}
int MMOD(int x,int y){x%=MOD;y%=MOD;return (x*y)%MOD;}
//int AMOD(int x,int y){x%=MOD;y%=MOD;return (x+y)%MOD;}
int SMOD(int x,int y){x%=MOD;y%=MOD;return (x-y+MOD)%MOD;}
//int Factorial[N];void FAC(){Factorial[0]=1;for(int i=1;i<=2e6;i++)Factorial[i]=(Factorial[i-1]%MOD*i%MOD)%MOD;}
//int PREFIX[3e6];void PFX(){PREFIX[0]=0;for(int i=1;i<=2e6;i++)PREFIX[i]=PREFIX[i]+PREFIX[i-1]+i;}
//fill_n(&a[0][0],(n+1)*(m+1),valu);
//int C(int x,int y){int A=1,B=1;for(int i=y+1;i<=x;i++)A*=i;for(int i=2;i<=x-y;i++)B*=i;return A/B;}

vector <pair <int , int>> v[N] ;
void slv()
{
    int n , m ;
    cin >> n >> m ;

    vector <int> a(n) , b(m) ;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i] ;
    for(int i = 0 ; i < m ; i++)
        cin >> b[i] ;

    sort(all(a)) ;
    sort(all(b)) ;

    if(n >= m)
    {
        int l = 0 , r = 1e16 ;
        while(l <= r)
        {
            int mid = l + (r - l) / 2 ;

            int l1 = 0 , r1 = 0 ;
            while(l1 < n && r1 < m)
            {
                if(abs(a[l1] - b[r1]) <= mid)
                    l1++ , r1++ ;
                else
                    l1++ ;
            }

            if(r1 == m)
                r = mid - 1 ;
            else
                l = mid + 1 ;
        }

        cout << r + 1 ;
    }
    else
    {
        int l = 0 , r = 1e16 ;
        while(l <= r)
        {
            int mid = l + (r - l) / 2 ;

            int l1 = 0 , r1 = 0 ;
            while(l1 < n && r1 < m)
            {
                if(abs(a[l1] - b[r1]) <= mid)
                    l1++ , r1++ ;
                else
                    r1++ ;
            }

            if(l1 == n)
                r = mid - 1 ;
            else
                l = mid + 1 ;
        }

        cout << r + 1 ;
    }
}
main()
{

    //FAST ;

    int t = 1 ;
    //cin >> t ;

    while(t--)
        slv() ;
}

//TLE Problem ?
/*
    -> const MOD
    -> const int
    -> FAST
    -> "/n" | endl
    -> array size
*/

//MLE Problem ?
/*
    -> array size()
    -> N ?
    -> long long
    -> define
    -> long long dp[1000][100000] ? ;
*/

//RTE problem ?
/*
    -> array size ?
    -> x / 0 ?
*/

Compilation message

cipele.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8096 KB Output is correct
2 Correct 69 ms 8272 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8284 KB Output is correct
2 Correct 68 ms 8480 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 7688 KB Output is correct
2 Correct 41 ms 7004 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7928 KB Output is correct
2 Correct 40 ms 7184 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7760 KB Output is correct
2 Correct 58 ms 7728 KB Output is correct