Submission #292521

#	Time	Username	Problem	Language	Result	Execution time	Memory
292521		dandrozavr	Wiring (IOI17_wiring)	C++14	100 / 100	87 ms	10348 KiB

wiring

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC comment("-Wl,--stack=200000000")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
#include "wiring.h"

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int N = r.size();
    int m = b.size();
    vector < pii > v;
    for (int i : r) v.pb({i, 0});
    for (int i : b) v.pb({i, 1});
    sort(v.begin(), v.end());
    int n = v.size();

    int dl[n] = {};
    int bsz[n] = {};
    ll sum[n] = {};

    for (int i = 0; i < n; ++i){
        int x = v[i].F;
        if (!i || v[i - 1].S != v[i].S)
            bsz[i] = 1; else
            bsz[i] = bsz[i - 1] + 1;
        if (v[i].S){
            int pos = lower_bound(r.begin(), r.end(), v[i].F) - r.begin();
            if (!pos)
                dl[i] = abs(x - r[pos]); else
            if (pos == n)
                dl[i] = abs(x - r[pos - 1]); else
                dl[i] = min(abs(x - r[pos - 1]), abs(x - r[pos]));
        } else{
            int pos = lower_bound(b.begin(), b.end(), v[i].F) - b.begin();
            if (!pos)
                dl[i] = abs(x - b[pos]); else
            if (pos == n)
                dl[i] = abs(x - b[pos - 1]); else
                dl[i] = min(abs(x - b[pos - 1]), abs(x - b[pos]));
        }
        sum[i] = x;
        if (i) sum[i] += sum[i - 1];
    }

    auto Sum = [&sum](int x, int y){
        if (!x) return sum[y];
        return sum[y] - sum[x - 1];
    };
    ll dp[n] = {};
    for (int i = 0; i < n; ++i){
        if (i) dp[i] = dp[i - 1] + dl[i]; else
               dp[i] = dl[i];
        int bk = bsz[i];
//        cout << bk _ dp[i] << " ";
        if (i - bk * 2 >= 0)
            dp[i] = min(dp[i], dp[i - bk * 2] + Sum(i - bk + 1, i) - Sum(i - 2 * bk + 1, i - bk)); else
        if (i - bk * 2 == -1)
            dp[i] = min(dp[i], Sum(i - bk + 1, i) - Sum(i - 2 * bk + 1, i - bk));
//        cout << dp[i] << " " << dl[i] << endl;
    }
    return dp[n - 1];
}


#ifdef Estb_probitie
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

}
#endif // Estb_probitie

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:54:9: warning: unused variable 'N' [-Wunused-variable]
   54 |     int N = r.size();
      |         ^
wiring.cpp:55:9: warning: unused variable 'm' [-Wunused-variable]
   55 |     int m = b.size();
      |         ^

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