이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
int N = r.size();
int M = b.size();
long long BIG = ((long long) INT_MAX) * (long long) 200000;
vector<pair<int, bool> > all_points;
for (int i = 0; i < N; i++){
all_points.push_back(make_pair(r[i], true));
}
for (int i = 0; i < M; i++){
all_points.push_back(make_pair(b[i], false));
}
sort(all_points.begin(), all_points.end());
vector<int> block_number (N + M, 0);
vector<bool> is_single_block (N + M, false);
for (int i = 1; i < N + M; i++){
if(all_points[i].second == all_points[i - 1].second){
block_number[i] = block_number[i - 1];
} else {
block_number[i] = block_number[i - 1] + 1;
}
}
if (block_number[0] != block_number[1]){
is_single_block[0] = true;
}
if (block_number[N + M - 1] != block_number[N + M - 2]){
is_single_block[N + M - 1] = true;
}
for (int i = 1; i < N + M - 1; i++){
if(block_number[i - 1] != block_number[i] && block_number[i + 1] != block_number[i]){
is_single_block[i] = true;
}
}
vector<long long> best_cost_left (N + M, BIG);
int current_point = 0;
while(block_number[current_point] == 0){
current_point++;
}
int left_pointer;
int left_size;
int right_size;
long long partial;
bool is_single;
int block_start;
for (int cp = current_point; cp < N + M; cp++){
if (block_number[cp] != block_number[cp - 1]){
left_pointer = cp - 1;
left_size = 1;
right_size = 1;
partial = 0;
is_single = is_single_block[left_pointer];
block_start = cp;
if (is_single){
partial += all_points[cp].first - all_points[left_pointer].first;
if (left_pointer == 0){
best_cost_left[cp] = min(best_cost_left[cp], partial);
} else {
best_cost_left[cp] = min(best_cost_left[cp], partial + min(best_cost_left[left_pointer], best_cost_left[left_pointer - 1]));
}
} else {
if (block_number[left_pointer] == 0){
left_pointer = 0;
for (int i = 0; i < cp; i++){
partial += all_points[cp].first - all_points[i].first;
}
left_size = cp - 1;
best_cost_left[cp] = partial;
} else {
best_cost_left[cp] = best_cost_left[left_pointer - 1] + all_points[cp].first - all_points[left_pointer].first;
partial = all_points[cp].first - all_points[left_pointer].first;
//cout << cp << ' ' << best_cost_left[cp] << endl;
while (left_pointer > 0 && block_number[left_pointer - 1] == block_number[left_pointer]){
if (all_points[cp].first - all_points[left_pointer - 1].first + partial + best_cost_left[left_pointer - 2] <= best_cost_left[cp]){
partial += all_points[cp].first - all_points[left_pointer - 1].first;
//cout << 'p' << partial << ' ' << left_pointer << endl;
left_pointer--;
left_size++;
best_cost_left[cp] = partial + best_cost_left[left_pointer - 1];
//cout << ' ' << best_cost_left[cp] << endl;
} else {
break;
}
}
}
}
} else {
//cout << cp << 'c' << best_cost_left[cp - 1] << endl;
right_size++;
if (is_single){
partial += all_points[cp].first - all_points[left_pointer].first;
if (left_pointer == 0){
best_cost_left[cp] = min(best_cost_left[cp], partial);
} else {
best_cost_left[cp] = min(best_cost_left[cp], partial + min(best_cost_left[left_pointer], best_cost_left[left_pointer - 1]));
}
} else {
best_cost_left[cp] = best_cost_left[cp - 1];
if (right_size <= left_size){
best_cost_left[cp] += all_points[cp].first - all_points[block_start].first;
} else {
best_cost_left[cp] += all_points[cp].first - all_points[block_start - 1].first;
}
while (left_pointer > 0 && block_number[left_pointer - 1] == block_number[left_pointer]){
long long reduced = best_cost_left[cp];
if (right_size >= left_size + 1){
reduced = reduced + all_points[block_start - 1].first - all_points[left_pointer - 1].first;
} else {
reduced = reduced + all_points[block_start].first - all_points[left_pointer - 1].first;
}
if (reduced + best_cost_left[left_pointer - 2] <= best_cost_left[cp]){
best_cost_left[cp] = reduced + best_cost_left[left_pointer - 2];
left_size++;
left_pointer--;
} else {
break;
}
}
}
}
//cout << cp << 'f' << best_cost_left[cp] << endl;
}
//cout << best_cost_left[N + M - 1] << endl;
return best_cost_left[N + M - 1];
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:60:9: warning: 'block_start' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | int block_start;
| ^~~~~~~~~~~
wiring.cpp:115:13: warning: 'is_single' may be used uninitialized in this function [-Wmaybe-uninitialized]
115 | if (is_single){
| ^~
wiring.cpp:114:23: warning: 'right_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
114 | right_size++;
| ~~~~~~~~~~^~
wiring.cpp:125:17: warning: 'left_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
125 | if (right_size <= left_size){
| ^~
wiring.cpp:55:9: warning: 'left_pointer' may be used uninitialized in this function [-Wmaybe-uninitialized]
55 | int left_pointer;
| ^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |