Submission #425978

# Submission time Handle Problem Language Result Execution time Memory
425978 2021-06-13T12:41:29 Z MOUF_MAHMALAT Wiring (IOI17_wiring) C++11
0 / 100
2 ms 1868 KB
#include "wiring.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define S second
#define F first
using namespace std;
typedef long long ll;
deque<pair<ll,bool> >v;
vector<int>a,b;
ll dp[200009],id[200009][2];
ll best(ll d)
{
    if(d>=v.size())
        return 0;
    ll &r=dp[d];
    if(r!=-1)
        return r;
    r=1e16;
    if(v[d].S==0)
    {
        ll x=upper_bound(all(b),v[d].F)-b.begin(),sum;
        if(x>0)
        {
            x--;
            sum=abs(b[x]-v[d].F);
            if(b[x]>=v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
            else
                r=min(r,best(d+1)+sum);
            x++;
        }
        if(x<b.size())
        {
            sum=abs(b[x]-v[d].F);
            if(b[x]>=v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
            else
                r=min(r,best(d+1)+sum);
        }
    }

    else
    {
        ll x=upper_bound(all(a),v[d].F)-a.begin(),sum;
        if(x>0)
        {
            x--;
            sum=abs(a[x]-v[d].F);
            if(a[x]>v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
            else
                r=min(r,best(d+1)+sum);
            x++;
        }
        if(x<a.size())
        {
            sum=abs(a[x]-v[d].F);
            if(a[x]>v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
            else
                r=min(r,best(d+1)+sum);
        }
    }
    return r;
}
long long min_total_length(vector<int> o1, vector<int>o2 )
{
    sort(all(o1));
    sort(all(o2));
    a=o1,b=o2;
    ll i=0,j=0;
    while(i<o1.size()&&j<o2.size())
    {
        if(o1[i]<=o2[j])
        {
            id[i][0]=v.size();
            v.push_back({o1[i++],0});
        }
        else
        {
            id[j][1]=v.size();
            v.push_back({o2[j++],1});
        }
    }
    while(i<o1.size())
    {
        id[i][0]=v.size();
        v.push_back({o1[i++],0});
    }
    while(j<o2.size())
    {
        id[j][1]=v.size();
        v.push_back({o2[j++],1});
    }
    memset(dp,-1,sizeof dp);
    return best(0);
}

Compilation message

wiring.cpp: In function 'll best(ll)':
wiring.cpp:13:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(d>=v.size())
      |        ~^~~~~~~~~~
wiring.cpp:32:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(x<b.size())
      |            ~^~~~~~~~~
wiring.cpp:55:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(x<a.size())
      |            ~^~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:72:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while(i<o1.size()&&j<o2.size())
      |           ~^~~~~~~~~~
wiring.cpp:72:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while(i<o1.size()&&j<o2.size())
      |                        ~^~~~~~~~~~
wiring.cpp:85:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     while(i<o1.size())
      |           ~^~~~~~~~~~
wiring.cpp:90:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     while(j<o2.size())
      |           ~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1868 KB 3rd lines differ - on the 1st token, expected: '25859', found: '25597'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB 3rd lines differ - on the 1st token, expected: '904', found: '889'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Incorrect 1 ms 1788 KB 3rd lines differ - on the 1st token, expected: '17703', found: '17658'
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1740 KB 3rd lines differ - on the 1st token, expected: '27', found: '22'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1868 KB 3rd lines differ - on the 1st token, expected: '25859', found: '25597'
2 Halted 0 ms 0 KB -