Submission #340561

#	Time	Username	Problem	Language	Result	Execution time	Memory
340561		FlashGamezzz	Wiring (IOI17_wiring)	C++11	38 / 100	29 ms	3564 KiB

wiring

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <utility>
#include "wiring.h"

using namespace std;

long long intv(long long l, long long r){
	return (l*(l+1)+r*(r+1))/2 - min(l, r);
}

long long min_total_length(vector<int> r, vector<int> b) {
	long long n = r.size(), m = b.size(), sum = 0;
	if (r[n-1] > n+m || b[m-1] > n+m){
		for (int i = 0; i < n; i++){
			sum += b[0]-r[i];
		}
		for (int i = 0; i < m; i++){
			sum += b[i]-r[n-1];
		}
		sum -= min(n, m) * (b[0]-r[n-1]);
		return sum;
	} else {
		vector<long long> ints; long long ci = 0; int rc = 0; bool red = false;
		for (int i = 1; i <= n+m; i++){
			if (r[rc] == i){
				if (!red){
					if (ci != 0){
						ints.push_back(ci); ci = 0;
					}
					red = true;
				}
				rc++;
			} else {
				if (red){
					if (ci != 0){
						ints.push_back(ci); ci = 0;
					}
					red = false;
				}
			}
			ci++;
		}
		ints.push_back(ci); long long last = ints[0];
		long long sum = 0;
		for (int i = 1; i < ints.size()-1; i++){
			if (ints[i] % 2 != 0){
				if (last * 2 > ints[i+1]){
					sum += intv(last, ints[i]/2+1); last = ints[i]/2;
				} else {
					sum += intv(last, ints[i]/2); last = ints[i]/2+1;
				}
			} else {
				sum += intv(last, ints[i]/2); last = ints[i]/2;
			}
		}
		sum += (intv(last, ints[ints.size()-1]));
		return sum;
	}
}

Compilation message (stderr)

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

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