oj.uz

Submission #1054222

# Submission time Handle Problem Language Result Execution time Memory
1054222 2024-08-12T07:44:47 Z kiryl_krutsko Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 348 KB 
#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 (way cur : vec) {
		if (cur.right < mid) {
			ans += (mid - cur.right) * 2;
			left++;
		}
		else if (cur.left > mid) {
			ans += (cur.left - mid) * 2;
			right++;
		}
		
	}
	//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;
	}
	else {
		cout << 0 << endl;
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -