Submission #136989

#	Time	Username	Problem	Language	Result	Execution time	Memory
136989		zoooma13	Wiring (IOI17_wiring)	C++14	38 / 100	100 ms	7020 KiB

wiring

#include "bits/stdc++.h"
#include "wiring.h"
using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f
#define all(v) (v).begin() ,(v).end()

long long nxt(vector<int>&v ,int srch){
    auto it = lower_bound(all(v) ,srch);
    return it == v.end() ? INF : *it;
}
long long bef(vector<int>&v ,int srch){
    auto it = lower_bound(all(v) ,srch);
    return it == v.begin() ? -INF : *prev(it);
}

long long min_total_length(vector<int> r ,vector<int> b) {
    vector <pair<int ,bool>> all;
    for(int&i : r)all.push_back({i ,0});
    for(int&i : b)all.push_back({i ,1});
    sort(all.begin() ,all.end());

    vector <int> A[] = {r ,b};
    deque <int> a[] = {deque<int>{r.begin() ,r.end()}
                      ,deque<int>{b.begin() ,b.end()}};

    long long ans = 0LL;
    for(int i=0; i<all.size(); i++){
        auto&c = all[i];
        if(a[c.second].empty() || a[c.second].front() > c.first){
            continue;
        }
        if(a[!c.second].empty()){
            ans += min(c.first-bef(A[!c.second] ,c.first) ,nxt(A[!c.second] ,c.first)-c.first);
            continue;
        }

        long long newop = a[!c.second].front();
        long long ssss =
        min(c.first-bef(A[!c.second] ,c.first)
          ,nxt(A[!c.second] ,c.first)-c.first)
       +min(newop-bef(A[c.second] ,newop)
          ,nxt(A[c.second] ,newop)-newop);

        if(newop-c.first < ssss){
            a[!c.second].pop_front();
            ans += newop-c.first;
        }else{
            ans += min(c.first-bef(A[!c.second] ,c.first) ,nxt(A[!c.second] ,c.first)-c.first);
        }

        a[c.second].pop_front();
    }

    return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<all.size(); i++){
                  ~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45