Submission #476132

#	Time	Username	Problem	Language	Result	Execution time	Memory
476132		aryan12	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	204 KiB

wiring

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

long long min_total_length(std::vector<int> red, std::vector<int> blue) {
	long long n = red.size(), m = blue.size();
	vector<array<long long, 2> > wirings;
	wirings.push_back({0, 0});
	for(long long i = 0; i < n; i++) {
		wirings.push_back({red[i], 0});
	}
	for(long long i = 0; i < m; i++) {
		wirings.push_back({blue[i], 1});
	}
	sort(wirings.begin() + 1, wirings.end());
	long long total = wirings.size();
	long long closest[total + 1];
	for(long long i = 0; i <= total; i++) {
		closest[i] = 1e9;
	}
	long long lastPoint[2] = {-1, -1};
	for(long long i = 1; i < wirings.size(); i++) {
		//cout << "Current color = " << ((wirings[i][1]) ? "blue, " : "red, ");
		if(lastPoint[1 - wirings[i][1]] != -1) {
			closest[i] = wirings[i][0] - wirings[lastPoint[1 - wirings[i][1]]][0];
		}
		//cout << "Last index of the other color = " << lastPoint[1 - wirings[i][1]] << "\n";
		lastPoint[wirings[i][1]] = i;
	}
	lastPoint[0] = -1;
	lastPoint[1] = -1;
	//cout << "Going in reverse\n";
	for(long long i = wirings.size() - 1; i > 0; i--) {
		//cout << "Current color = " << ((wirings[i][1]) ? "blue, " : "red, ");
		if(lastPoint[1 - wirings[i][1]] != -1) {
			closest[i] = min(closest[i], wirings[lastPoint[1 - wirings[i][1]]][0] - wirings[i][0]);
		}
		//cout << "Last index of the other color = " << lastPoint[1 - wirings[i][1]] << "\n";
		lastPoint[wirings[i][1]] = i;
	}
	/*cout << "Outputting all the points, along with their colors:\n";
	for(int i = 1; i < wirings.size(); i++) {
		cout << wirings[i][0] << " " << ((wirings[i][1]) ? "blue" : "red") << "\n";
	}*/
	/*cout << "Outputting the closest array\n";
	for(int i = 1; i < total; i++) {
		cout << closest[i] << " ";
	}
	cout << "\n";*/
	map<int, int> lastSeen;
	int pref[total + 1], prev[total + 1];
	pref[0] = 0;
	int cur_abs_value = 0;
	for(int i = 1; i < wirings.size(); i++) {
		//cout << "i = " << i << ", cur_abs_value before: " << cur_abs_value << ", ";
		if(wirings[i][1] == 0) {
			cur_abs_value++;
			pref[i] = pref[i - 1] + wirings[i][0];
		}
		else {
			cur_abs_value--;
			pref[i] = pref[i - 1] - wirings[i][0];
		}
		if(!lastSeen.count(cur_abs_value)) {
			prev[i] = -1;
		}
		else {
			prev[i] = lastSeen[cur_abs_value];
		}
		lastSeen[cur_abs_value] = i;
		//cout << "cur_abs_value after: " << cur_abs_value << "\n";
	}
	long long dp[total + 1];
	for(long long i = 0; i <= total; i++) {
		dp[i] = 0;
	}
	for(long long i = 1; i < wirings.size(); i++) {
		dp[i] = dp[i - 1] + closest[i];
		if(prev[i] != -1) {
			dp[i] = min(dp[i], dp[prev[i]] + abs(pref[i] - pref[prev[i]]));
		}
	}
	/*for(long long i = 1; i < wirings.size(); i++) {
		cout << dp[i] << " ";
	}
	cout << "\n";*/
	return dp[total - 1] - dp[1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:22:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(long long i = 1; i < wirings.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~~
wiring.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 1; i < wirings.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
wiring.cpp:77:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(long long i = 1; i < wirings.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~~

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