Submission #618053

#	Time	Username	Problem	Language	Result	Execution time	Memory
618053		Ozy	Wiring (IOI17_wiring)	C++17	13 / 100	48 ms	16796 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define INF (1ll << 60)

lli apu,pos,res,last[2],otro,dis,doble,n;
vector<pair<lli,lli> > g1,g2,orden;
vector<lli> izq,der,MIN;

long long min_total_length(std::vector<int> r, std::vector<int> b) {

    for (auto act : r) orden.push_back({act,0});
    for (auto act : b) orden.push_back({act,1});
    sort(orden.begin(), orden.end());

    apu = 0;
    n = orden.size();

    last[0] = INF;
    last[1] = INF;
    izq.resize(n);
    rep(i,0,n-1) {
        last[orden[i].second] = orden[i].first;
        otro = orden[i].second^1;

        if (last[otro] != INF) izq[i] = orden[i].first - last[otro];
        else izq[i]= INF;
    }

    last[0] = INF;
    last[1] = INF;
    der.resize(n);
    repa(i,n-1,0) {
        last[orden[i].second] = orden[i].first;
        otro = orden[i].second^1;
        der[i] = last[otro] - orden[i].first;
    }

    MIN.resize(n);
    rep(i,0,n-1) MIN[i] = min(izq[i],der[i]);

    res = 0;
    while (apu < n) {

        g2.push_back({orden[apu].first,apu});
        apu++;
        while (apu < n && orden[apu].second == orden[apu-1].second) {g2.push_back({orden[apu].first, apu}); apu++;}

        pos = 0;
        while (pos < g1.size() && pos < g2.size()) {

            dis = g2[pos].first - g1[pos].first;
            doble =MIN[g2[pos].second] + MIN[g1[pos].second];

            if (doble < dis) break;

            res += dis;
            pos++;
        }

        if (!g1.empty()) rep(i,pos,g1.size()-1) res += MIN[g1[i].second];

        g1.clear();
        if (!g2.empty()) repa(i,g2.size()-1,pos) g1.push_back(g2[i]);
        g2.clear();

        //for (auto act : g1) {debugsl(act.first); debug(act.second);}
        //cout << endl;

    }
    for (auto act : g1) res += MIN[act.second];

    return res;

}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:56:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (pos < g1.size() && pos < g2.size()) {
      |                ~~~~^~~~~~~~~~~
wiring.cpp:56:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (pos < g1.size() && pos < g2.size()) {
      |                                   ~~~~^~~~~~~~~~~
wiring.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
wiring.cpp:67:26: note: in expansion of macro 'rep'
   67 |         if (!g1.empty()) rep(i,pos,g1.size()-1) res += MIN[g1[i].second];
      |                          ^~~

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