Submission #234418

#	Time	Username	Problem	Language	Result	Execution time	Memory
234418		aggu_01000101	Wiring (IOI17_wiring)	C++14	13 / 100	168 ms	22544 KiB

wiring

#include <bits/stdc++.h>
#define int long long
#define INF 10000000000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
int min_total_length(vector<signed> r, vector<signed> b){
    if(r.size()>b.size()) swap(r, b);
    int cost = 0;
    map<int, int> mp;
    set<int> s;
    for(int i: r){
        auto it = upper_bound(b.begin(), b.end(), i);
        int near = INF;
        bool pos = true;
        if(it!=b.end()) near = min(near, (*it) - i);
        if(it!=b.begin()){
            it--;
            if((i - (*it))<near){
                pos = false;
                near = (i - (*it));
            }
        }
        //cout<<i<<" "<<near<<endl;
        cost+=near;
        if(!pos) near*=-1;
        mp[i + near]++;
        if(mp[i+near]>=2) s.insert((i+near));
        s.insert(i);
        mp[i] = INF;
    }
    for(int i: b){
        if(mp[i]>0) continue;
        auto it = s.upper_bound(i);
        int near = INF;
        bool pos = true;
        if(it!=s.end()) near = min(near, (*it) - i);
        if(it!=s.begin()){
            it--;
            if((i - (*it))<near){
                pos = false;
                near = (i - (*it));
            }
        }
        //cout<<i<<" "<<near<<endl;
        cost+=near;
        if(!pos) near*=-1;
        mp[i + near]--;
        if(mp[i+near]<=1) s.erase((i+near));
    }
    return cost;
}
/*signed main(){
    int n, m;
    cin>>n>>m;
    vector<signed> a;
    vector<signed> b;
    for(int i = 0;i<n;i++){
        int num;
        cin>>num;
        a.push_back(num);
    }
    for(int i = 0;i<m;i++){
        cin>>n;
        b.push_back(n);
    }
    cout<<min_total_length(a, b)<<endl;
}*/

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