Submission #136581

#	Time	Username	Problem	Language	Result	Execution time	Memory
136581		wilwxk	Wiring (IOI17_wiring)	C++14	13 / 100	111 ms	16920 KiB

wiring

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

const int MAXN=4e5+5;
map<int, int> mp;
int cor[MAXN];
ll dist[MAXN];
ll dp[MAXN][2];
int n, x, y;
ll respf;

void calc(vector<int> &ult, vector<int> &atual) {
	if(ult.empty()||atual.empty()) return;
	// printf("calc\n"); respf=0;
	// for(auto cur : ult) printf("%d ", cur); cout << endl;
	// for(auto cur : atual) printf("%d ", cur); cout << endl;

	int ind=0;
	while(ind<ult.size()&&ind<atual.size()) {
		ll aa=ult[ult.size()-ind-1]; ll bb=atual[ind];
		respf+=abs(dist[aa]-dist[bb]);
		ind++;
	}

	for(int i=ind; i<atual.size(); i++) respf+=abs(dist[atual[i]]-dist[ult.back()]);
	for(int i=ult.size()-ind-1; i>=0; i--) respf+=abs(dist[ult[i]]-dist[atual[0]]);
}

ll min_total_length(vector<int> R, vector<int> B) {
	respf=0;
	x=R.size(); y=B.size(); n=x+y;
	for(auto cur : R) mp[cur]=0;
	for(auto cur : B) mp[cur]=1;
	int conti=1; for(auto &mit : mp) {
		cor[conti]=mit.second;
		dist[conti]=mit.first;
		mit.second=conti++;
	}
	cor[n+1]=-1;
	vector<int> ult, cur;
	for(int i=1; i<=n; i++) {
		if(cor[i]==cor[i+1]) cur.push_back(i);
		else {
			cur.push_back(i);
			calc(ult, cur);
			ult.clear();
			swap(cur, ult);
		}
	}

	// respf=

	return respf;
}

Compilation message (stderr)

wiring.cpp: In function 'void calc(std::vector<int>&, std::vector<int>&)':
wiring.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ind<ult.size()&&ind<atual.size()) {
        ~~~^~~~~~~~~~~
wiring.cpp:21:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ind<ult.size()&&ind<atual.size()) {
                        ~~~^~~~~~~~~~~~~
wiring.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=ind; i<atual.size(); i++) respf+=abs(dist[atual[i]]-dist[ult.back()]);
                 ~^~~~~~~~~~~~~

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