Submission #1054179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054179		kiryl_krutsko	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	348 KiB

bridge

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct way {
  int left, right;
  way(int n1, int n2) {
    left = min(n1, n2);
    right = max(n1, n2);
  }
};

int bs(int start, int end, vector<way>* vec, int start_ans) {
  int ans = start_ans;
  int right = 0;
  int left = 0;
  int mid = (start + end) / 2;
  //cout << mid << " : ";
  for (int i = 0; i < vec->size();i++) {
    way cur = vec->at(i);
    if (cur.right < mid) {
      ans += (mid - cur.right) * 2;
      left++;
    }
    else if (cur.left > mid) {
      ans += (cur.left - mid) * 2;
      right++;
    }
    else if (cur.left<start && cur.right>start) {
      vec->erase(vec->begin() + i);
      i--;
    }
  }
  //cout << left << " " << right << " " << endl << "ans : " << ans << endl;
  if (right == left || start == end) {
    //cout << mid << endl;
    return ans;
  }
  else if (right > left) {
    return bs(mid + 1, end, vec, start_ans);
  }
  else {
    return bs(start, mid, vec, start_ans);
  }
}

int main()
{
  int n, k, ans;
  cin >> k >> n;
  ans = 0;
  vector<way> vec;
  int n1, n2;
  char t1, t2;
  int max = 0;
  int min = 1000000001;
  for (int i = 0; i < n; i++) {
    cin >> t1 >> n1 >> t2 >> n2;
    ans += abs(n1 - n2);
    if (t1 != t2) {
      ans++;
      way w = way(n1, n2);
      if (w.left < min) min = w.left;
      if (w.right > max) max = w.right;
      vec.push_back(w);
    }
  }
  if (k == 1) {
    cout << bs(min, max, &vec, ans) << endl;
  }
}

Compilation message (stderr)

bridge.cpp: In function 'int bs(int, int, std::vector<way>*, int)':
bridge.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<way>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 0; i < vec->size();i++) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37