# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
73254 |
2018-08-28T06:01:45 Z |
nvmdava |
Wiring (IOI17_wiring) |
C++17 |
|
3 ms |
468 KB |
#include "wiring.h"
#define INF 2000000005
#include <bits/stdc++.h>
using namespace std;
struct Path{
int r, b, len;
Path(int _r, int _b, int _len){
r = _r;
b = _b;
len = _len;
}
bool operator<(const Path& rhs) const{
return len < rhs.len;
}
};
vector<Path> v;
int rr[100007], bb[100007];
int conr[100007], conb[100007];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
r.push_back(INF);
b.push_back(INF);
bb[0] = 0;
rr[0] = 0;
long long ans = 0;
for(int i = 1; i < b.size(); i++){
bb[i] = upper_bound(r.begin() + bb[i - 1], r.end(), (b[i] + b[i - 1]) / 2) - r.begin();
}
for(int i = 1; i < r.size(); i++){
rr[i] = upper_bound(b.begin() + rr[i - 1], b.end(), (r[i] + r[i - 1]) / 2) - b.begin();
}
for(int i = 0; i < b.size(); i++){
for(int j = bb[i]; j < bb[i + 1]; j++){
v.push_back(Path(j, i, abs(r[j] - b[i])));
}
}
for(int i = 0; i < r.size(); i++){
for(int j = rr[i]; j < rr[i + 1]; j++){
v.push_back(Path(i, j, abs(r[i] - b[j])));
}
}
sort(v.begin(), v.end());
for(auto x : v){
if(conr[x.r] * conb[x.b] == 0){
conr[x.r]++;
conb[x.b]++;
ans += x.len;
}
}
return ans;
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < b.size(); i++){
~~^~~~~~~~~~
wiring.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < r.size(); i++){
~~^~~~~~~~~~
wiring.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < b.size(); i++){
~~^~~~~~~~~~
wiring.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < r.size(); i++){
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
252 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '41560' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
356 KB |
3rd lines differ - on the 1st token, expected: '904', found: '946' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
432 KB |
3rd lines differ - on the 1st token, expected: '316', found: '356' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
468 KB |
3rd lines differ - on the 1st token, expected: '27', found: '29' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
252 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '41560' |
2 |
Halted |
0 ms |
0 KB |
- |