oj.uz

Submission #332556

# Submission time Handle Problem Language Result Execution time Memory
332556 2020-12-02T21:26:04 Z MetB Wiring (IOI17_wiring) C++14
0 / 100
 63 ms 8944 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const int N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

ll d[N];

void process(vector<ll>& fst, vector<ll>& snd, ll from) {
	if(fst.empty()) return;

	vector<ll> dleft(fst.size() + snd.size() + 1, INF);
	vector<ll> dright(fst.size() + snd.size() + 1, INF);

	from -= (ll)fst.size() + (ll)snd.size();
	
	ll dist = snd[0] - fst.back();
	ll sum_len = 0, sz = 0;

	for (ll i = fst.size(); i >= 0; i--) {
		ll last = (i + from ? d[i + from - 1] : 0);

		if (i != fst.size()) sum_len += fst.back() - fst[i];

		dleft[sz] = last + sum_len;
		dright[sz] = last + sum_len + sz * dist;
		sz++;
	}

	for (ll i = 1; i <= snd.size(); i++) {
		dleft[i] = min(dleft[i-1], dleft[i]);
	}

	for (ll i = snd.size() - 1; i >= 0; i--) {
		dright[i] = min(dright[i+1], dright[i]);
	}

	sum_len = 0;

	from += (ll)fst.size();
	for (ll i = 0; i < snd.size(); i++) {
		sum_len += snd[i] - snd[0];
		d[i + from] = sum_len;
		d[i + from] += min(dright[i+1], dleft[i+1] + (i + 1) * dist);
	}
}

ll min_total_length(vector<int> r, vector<int> b) {
	auto pr = r.begin(), pb = b.begin();

	ll n = r.size() + b.size();

	fill(d, d + n, INF);

	struct poll {
		ll x;
		char color;

		bool operator<(poll b) {
			return x < b.x;
		}
	};

	vector<poll> v;
	vector<ll> red, blue;

	for (ll a : r) {
		v.push_back({a, 'r'});
	}

	for (ll a : b) {
		v.push_back({a, 'b'});
	}

	sort(v.begin(), v.end());

	for (ll i = 0; i < n; i++) {
		if (i && v[i-1].color != v[i].color) {
			if (v[i].color == 'r') {
				process(red, blue, i);
				red.clear();
			}
			else {
				process(blue, red, i);
				blue.clear();
			}
		}

		if (v[i].color == 'r') red.push_back(v[i].x);
		else blue.push_back(v[i].x);
	}

	if(v.back().color == 'r') process(blue, red, n);
	else process(red, blue, n);

	return d[v.size() - 1];
}

/*ll main () {
	ll sr, sb;
	cin >> sr >> sb;

	vector<ll> r, b;

	for (ll i = 0; i < sr; i++) {
		ll x;
		cin >> x;
		r.push_back(x);
	}

	for (ll i = 0; i < sb; i++) {
		ll x;
		cin >> x;
		b.push_back(x);
	}

	cout << min_total_length(r, b);
}*/

Compilation message

wiring.cpp: In function 'void process(std::vector<long long int>&, std::vector<long long int>&, ll)':
wiring.cpp:32:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if (i != fst.size()) sum_len += fst.back() - fst[i];
      |       ~~^~~~~~~~~~~~~
wiring.cpp:39:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (ll i = 1; i <= snd.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
wiring.cpp:50:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (ll i = 0; i < snd.size(); i++) {
      |                 ~~^~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:58:7: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
   58 |  auto pr = r.begin(), pb = b.begin();
      |       ^~
wiring.cpp:58:23: warning: variable 'pb' set but not used [-Wunused-but-set-variable]
   58 |  auto pr = r.begin(), pb = b.begin();
      |                       ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 3rd lines differ - on the 1st token, expected: '904', found: '1000000000000000326'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 59 ms 7644 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1000000000000016523'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 63 ms 8944 KB 3rd lines differ - on the 1st token, expected: '373710605', found: '409801698'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -