제출 #1199413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199413		lrnnz	전선 연결 (IOI17_wiring)	C++20	0 / 100	0 ms	332 KiB

wiring

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "wiring.h"
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
 
template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}
void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}

template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

#define nl "\n"
#define sp << " " <<

/********* DEBUG *********/

const ll MOD = 1000000007;
const ll inf = 1e18;
const ll mxN = 1000005;

ll min_total_length(vector<int> r, vector<int> b) {
    ll rptr = r[0] < b[0], bptr = b[0] < r[0], n = sz(r), m = sz(b);

    ll ans = 0;
    vector<ll> tempr(n), tempb(m);
    stack<ll> unpairR, unpairB;

    if (rptr)
        unpairR.push(0);
    else
        unpairB.push(0);

    for (int i = 1; i < n+m; i++){
        if (rptr < n && (bptr == m || r[rptr] < b[bptr])){
            // do red
            if (sz(unpairB)){
                ll x = unpairB.top();
                unpairB.pop();

                ans-=tempb[x]-(r[rptr]-b[x]);
            }
            else{
                ll val = r[rptr] - b[max((ll)0, bptr-1)];
                ans+=val;
                tempr[rptr] = val;
                
                unpairR.push(rptr);
            }
            rptr++;
        }
        else{
            // do blue
            if (sz(unpairR)){
                ll x = unpairR.top();
                unpairR.pop();

                ans-=tempr[x]-(b[bptr]-r[x]);
            }
            else{
                ll val = b[bptr] - r[max((ll)0, rptr-1)];
                ans+=val;
                tempb[bptr] = val;
                
                unpairB.push(bptr);
            }
            bptr++;
        }

        //outval("i,ans:",i,ans);
    }

    return ans;
}

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