Submission #497298

#	Time	Username	Problem	Language	Result	Execution time	Memory
497298		kevin	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	336 KiB

wiring

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define ca(v) for(auto i:v) cout<<i<<" ";
#define nl cout<<"\n"

const int MAXN = 5e5 + 5;

ll min_total_length(vector<int> a, vector<int> b){
    vector<pair<ll, int>> ar;
    for(int i:a) ar.push_back({(ll)i, 0});
    for(int i:b) ar.push_back({(ll)i, 1});
    sort(ar.begin(), ar.end());
    int p = 0;
    int pv = -1;
    vector<ll> val[2];
    // 0 = <, 1 = >, so add
    // 0 is pref, 1 is posts
    while(p < ar.size()){
        vector<ll> v;
        ll x = ar[p].f;
        v.push_back(x);
        while(p < ar.size() - 1 && ar[p].s == ar[p+1].s) v.push_back(ar[++p].s);
        p++;
        ll iv = (p == ar.size()?0:ar[p].f-x);
        if(pv == -1){
            val[0] = val[1] = vector<ll>(v.size() + 1, 1e18);
            ll sm = 0;
            for(ll i:v) sm = sm + i;
            val[0][v.size()-1] = val[1][v.size()-1] = sm;
            val[1][v.size()-1] += iv * v.size();
        }
        else{
            vector<ll> nxt[2]; nxt[0] = nxt[1] = vector<ll>(v.size() + 1);
            for(int i=0; i<=v.size(); i++){
                nxt[v.size()-i][0] = min(val[i][0] + i * (x - pv), val[i][1]);
                nxt[v.size()-i][1] = nxt[v.size()-i][0] + i * (iv - x);
            }
            val[0] = nxt[0];
            val[1] = nxt[1];
            nxt[0].clear(); nxt[1].clear();
        }
        pv = x;
        for(int i=1; i<val[0].size(); i++){
            val[0][i] = min(val[0][i], val[0][i-1]);
            val[0][val[0].size()-1-i] = min(val[0][val[0].size()-1-i], val[0][val[0].size()-i]);
        }
    }
    return val[0].back();
}

// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
    
// }

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while(p < ar.size()){
      |           ~~^~~~~~~~~~~
wiring.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(p < ar.size() - 1 && ar[p].s == ar[p+1].s) v.push_back(ar[++p].s);
      |               ~~^~~~~~~~~~~~~~~
wiring.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         ll iv = (p == ar.size()?0:ar[p].f-x);
      |                  ~~^~~~~~~~~~~~
wiring.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int i=0; i<=v.size(); i++){
      |                          ~^~~~~~~~~~
wiring.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=1; i<val[0].size(); i++){
      |                      ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45