oj.uz

답안 #373176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373176 2021-03-03T15:43:06 Z Doxeno 전선 연결 (IOI17_wiring) C++17
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;

ll min_total_length(vector<int> r, vector<int> b){
    int N = r.size(), M = b.size();
    int ind = 0;
    set<int> rs[N], bs[M];
    for(int i = 0; i < N; i++){
        while(ind < M-1 && b[ind] < r[i])ind++;
        if(ind == 0){rs[i].insert(0); bs[0].insert(i);}
        else{
            if(abs(b[ind] - r[i]) <= abs(b[ind-1] - r[i])){rs[i].insert(ind); bs[ind].insert(i);}
            if(abs(b[ind] - r[i]) >= abs(b[ind-1] - r[i])){rs[i].insert(ind-1); bs[ind-1].insert(i);}
        }
    }
    ind = 0;
    for(int i = 0; i < M; i++){
        while(ind < N-1 && r[ind] < b[i])ind++;
        if(ind == 0){bs[i].insert(0); rs[0].insert(i);}
        else {
            if(abs(r[ind] - b[i]) <= abs(r[ind-1] - b[i])){bs[i].insert(ind); rs[ind].insert(i);}
            if(abs(r[ind] - b[i]) >= abs(r[ind-1] - b[i])){bs[i].insert(ind-1); rs[ind-1].insert(i);}
        }
    }
    int ri = 0, bi = 0;
    for(int kekw = 0; kekw < M+N; kekw++){
        if(bi >= M || ri < N && r[ri] < b[bi]){
            vector<int> k;
            for(auto x: rs[ri]){
                if(k.size() < rs[ri].size()-1 && bs[x].size() > 1){
                    k.pb(x);
                }
            }
            for(auto x: k){rs[ri].erase(x); bs[x].erase(ri);}
            ri++;
        }else{
            vector<int> k;
            for(auto x: bs[bi]){
                if(k.size() < bs[bi].size()-1 && rs[-x].size() > 1){
                    k.pb(x);
                }
            }
            for(auto x: k){bs[bi].erase(x); rs[x].erase(bi);}

            bi++;
        }
    }
    ll ans = 0;
    for(int i = 0; i < N; i++){
        for(auto x: rs[i])ans += abs(r[i]-b[x]);
    }
    return ans;
}

Compilation message

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |         if(bi >= M || ri < N && r[ri] < b[bi]){

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '25859', found: '30835'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '904', found: '888'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '316', found: '348'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '27', found: '22'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '25859', found: '30835'
2 Halted 0 ms 0 KB -