oj.uz

Submission #660584

# Submission time Handle Problem Language Result Execution time Memory
660584 2022-11-22T13:18:00 Z Banan Wiring (IOI17_wiring) C++17
13 / 100
 84 ms 9904 KB 
#include "wiring.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define double long double
#define endl '\n'
#define sz(a) (int)a.size()
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
ll const INF = LONG_LONG_MAX;



long long min_total_length(std::vector<int> r, std::vector<int> b) {

    ll n=sz(r), m=sz(b);
    if(n>m){swap(n, m);swap(r, b);}
    set<ll, greater<>> decr;
    for(int i=0;i<m;i++)
    {
        decr.insert(b[i]);
    }
    map<int, bool> mark;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        auto it=decr.lower_bound(r[i]);
        if(it==decr.end()){it--;}
        ll v=(*it);
        ans+=abs(v-r[i]);
        decr.erase(v);
        mark[v]=1;
    }

    for(int i=0;i<m;i++)
    {
        if(!mark[b[i]])
        {
            int lo=0, hi=n-1, mid=(lo+hi)/2, ind1=-1;
            while(lo<=hi)
            {
                if(r[mid]<b[i]){ind1=mid;lo=mid+1;mid=(lo+hi)/2;}
                else{hi=mid-1;mid=(lo+hi)/2;}
            }
            lo=0, hi=n-1, mid=(lo+hi)/2;
            int ind2=-1;
            while(lo<=hi)
            {
                if(r[mid]>b[i]){ind2=mid;hi=mid-1;mid=(lo+hi)/2;}
                else{lo=mid+1;mid=(lo+hi)/2;}
            }
            if(ind1==-1){ans+=abs(r[ind2]-b[i]);}
            else if(ind2==-1){ans+=abs(r[ind1]-b[i]);}
            else{ans+=max(abs(r[ind2]-b[i]), abs(r[ind1]-b[i]));}
        }
    }

	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '14340', found: '17422'
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 62 ms 9872 KB Output is correct
4 Correct 60 ms 9904 KB Output is correct
5 Correct 65 ms 9852 KB Output is correct
6 Correct 70 ms 8488 KB Output is correct
7 Correct 68 ms 8488 KB Output is correct
8 Correct 73 ms 8488 KB Output is correct
9 Correct 84 ms 8500 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '17703', found: '19052'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '27', found: '30'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '14340', found: '17422'
3 Halted 0 ms 0 KB -