#include "wiring.h"
using namespace std;
long long best[200000][3][2];
long long next_different[200000];
long long last_different[200000];
long long inline mmin(long long a,long long b)
{
if(a<b)
{
return a;
}
return b;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int r_idx=0,b_idx=0,place=0;
bool red;
long long next_of_kind[2];
long long last_of_kind[2];
vector<pair<int,int>> pole(r.size()+b.size());
while((r_idx<r.size())||(b_idx<b.size()))
{
if(r_idx>=r.size())
{
red=false;
}
else if(b_idx>=b.size())
{
red=true;
}
else
{
red=r[r_idx]<b[b_idx];
}
if(red)
{
pole[place]=make_pair(0,r[r_idx]);
r_idx++;
}
else
{
pole[place]=make_pair(1,b[b_idx]);
b_idx++;
}
place++;
}
next_of_kind[0]=3000000000;
next_of_kind[1]=next_of_kind[0];
last_of_kind[0]=-next_of_kind[0];
last_of_kind[1]=last_of_kind[0];
for(int i=0;i<pole.size();i++)
{
last_of_kind[pole[i].first]=pole[i].second;
last_different[i]=last_of_kind[1-pole[i].first];
}
for(int i=pole.size()-1;i>=0;i--)
{
next_of_kind[pole[i].first]=pole[i].second;
next_different[i]=next_of_kind[1-pole[i].first];
}
for(int i=0;i<pole.size();i++)
{
if(i==0)
{
best[i][0][0]=next_different[i]-pole[i].second;
best[i][1][0]=pole[i].second-last_different[i];
best[i][2][0]=best[i][0][0];
best[i][0][1]=best[i][0][0];
best[i][1][1]=best[i][1][0];
best[i][2][1]=best[i][2][0];
}
else
{
if(pole[i].first==pole[i-1].first)
{
best[i][0][0]=mmin(best[i-1][2][0]+next_different[i]-pole[i].second,best[i-1][0][1]+pole[i].second-last_different[i]);
best[i][1][0]=best[i-1][1][1]+pole[i].second-last_different[i];
best[i][0][1]=mmin(best[i-1][2][1]+next_different[i]-pole[i].second,best[i-1][0][1]+pole[i].second-last_different[i]);
best[i][1][1]=best[i][1][0];
}
else
{
best[i][0][0]=best[i-1][2][0]+next_different[i]-pole[i].second;
best[i][1][0]=best[i-1][0][0];
if(i==1)
{
best[i][0][1]=next_different[i]-pole[i].second;
best[i][1][1]=pole[i].second-last_different[i];
}
else
{
if(pole[i].first==pole[i-2].first)
{
best[i][0][1]=best[i-2][2][0]+next_different[i]-pole[i].second;
best[i][1][1]=best[i-2][2][0]+pole[i].second-last_different[i];
}
else
{
best[i][0][1]=best[i-2][2][0]+next_different[i]-pole[i].second;
best[i][1][1]=best[i-2][0][0];
}
}
}
best[i][2][0]=mmin(best[i][0][0],best[i][1][0]);
best[i][2][1]=mmin(best[i][0][1],best[i][1][1]);
}
}
return best[pole.size()-1][2][0];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((r_idx<r.size())||(b_idx<b.size()))
~~~~~^~~~~~~~~
wiring.cpp:24:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((r_idx<r.size())||(b_idx<b.size()))
~~~~~^~~~~~~~~
wiring.cpp:26:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(r_idx>=r.size())
~~~~~^~~~~~~~~~
wiring.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if(b_idx>=b.size())
~~~~~^~~~~~~~~~
wiring.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<pole.size();i++)
~^~~~~~~~~~~~
wiring.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<pole.size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37607' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
356 KB |
3rd lines differ - on the 1st token, expected: '904', found: '943' |
| 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: '348' |
| 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: '27', found: '28' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37607' |
| 2 |
Halted |
0 ms |
0 KB |
- |
