Submission #1061158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061158		vjudge1	Wiring (IOI17_wiring)	C++17	13 / 100	24 ms	5344 KiB

wiring

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll min_total_length(vector<int> r, vector<int> b)
{
  if(r.size() > b.size()) swap(r, b);
  
  int n = r.size(), m = b.size();

  vector<pair<int,int> > vec;

  for(int i = 0; i < n; i ++)
    vec.push_back({r[i], 0});

  for(int i = 0; i < m; i ++)
    vec.push_back({b[i], 1});
  sort(vec.begin(), vec.end());
  long long ans = 0;
  vector<pair<int,int> > st;
  for(int i = 0; i < vec.size(); i ++)
    {
      if(st.empty() || st.back().second == vec[i].second)
	st.push_back(vec[i]);
      else
	{
	  ans += vec[i].first - st.back().first;
	  st.pop_back();
	}
    }
 
  for(auto [x, y] : st)
    {
      int i = upper_bound(r.begin(), r.end(), x) - r.begin();
      int c = 2e9;
      if(i < r.size())
	c = min(r[i] - x, c);
      i--;
      if(i >= 0)
	c = min(x - r[i], c);
      ans += c;
      //   cerr << c << endl;
    }
  
  return ans;
}
/*
int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m);
  for(int i = 0; i < n; i ++) cin >> a[i];
  for(int i = 0; i < m ; i ++) cin >> b[i];

  cout << min_total_length(a, b);
  return 0;
}
// */

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i = 0; i < vec.size(); i ++)
      |                  ~~^~~~~~~~~~~~
wiring.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       if(i < r.size())
      |          ~~^~~~~~~~~~

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