oj.uz

Submission #1083191

# Submission time Handle Problem Language Result Execution time Memory
1083191 2024-09-02T17:42:55 Z damamila Palembang Bridges (APIO15_bridge) C++17
22 / 100
 33 ms 6992 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int k, n;
	cin >> k >> n;
	int m = 0;
	vector<tuple<int, int, int>> num;
	vector<int> all;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		char c, d;
		cin >> c >> a >> d >> b;
		if (c == d) {
			ans += abs(b-a);
		} else {
			m++;
			ans++;
			all.push_back(a);
			all.push_back(b);
			num.push_back({a+b, a, b});
		}
	}
	sort(all.begin(), all.end());
	if (k == 1) {
		int x = all[all.size()/2];
		for (int i : all) {
			ans += abs(i-x);
		}
		cout << ans << endl;
	} else {
		sort(num.begin(), num.end());
		multiset<int> rbig;
		multiset<int> rsmall;
		multiset<int> lbig;
		multiset<int> lsmall;
		int rbigsum = 0, lbigsum = 0, rsmallsum = 0, lsmallsum = 0;
		for (int i = 0; i < all.size(); i++) {
			if (i <= all.size()/2) {
				rsmall.insert(all[i]);
				rsmallsum += all[i];
			} else {
				rbig.insert(all[i]);
				rbigsum += all[i];
			}
		}
		auto it = rsmall.end(); it--;
		int rmed = *it, lmed = 1e9;
		int res = 1e9; //biggest
		//~ cout << "YAYYYYY " << num.size() << endl;
		for (int i = 0; i < m-1; i++) {
			//~ cout << m << " " << i << endl;
			int tmp = 0; //ans for now
			auto [tot, a, b] = num[i];
			//remove from right
			if (a <= rmed) {
				rsmall.erase(rsmall.find(a));
				rsmallsum -= a;
			} else {
				rbig.erase(rbig.find(a));
				rbigsum -= a;
			}
			if (b <= rmed) {
				rsmall.erase(rsmall.find(b));
				rsmallsum -= b;
			} else {
				rbig.erase(rbig.find(b));
				rbigsum -= b;
			}
			//equalize right array lengths
			while (rbig.size() > rsmall.size()) {
				auto it = rbig.begin();
				rsmall.insert(*it);
				rbigsum -= *it;
				rsmallsum += *it;
				rbig.erase(rbig.begin());
			} 
			while (rsmall.size() > rbig.size()) {
				auto it = rsmall.end(); it--;
				rbig.insert(*it);
				rbigsum += *it;
				rsmallsum -= *it;
				rsmall.erase(it);
			}
			auto it = rsmall.end(); it--;
			int rmed = *it;
			//~ cout << "R DONE" << endl;
			//add to left
			if (a <= lmed) {
				lsmall.insert(a);
				lsmallsum += a;
			} else {
				lbig.insert(a);
				lbigsum += a;
			}
			if (b <= rmed) {
				lsmall.insert(b);
				lsmallsum += b;
			}
			else {
				lbig.insert(b);
				lbigsum += b;
			}
			//equalize left array lengths
			while (lbig.size() > lsmall.size()) {
				auto it = lbig.begin();
				lsmall.insert(*it);
				lsmallsum += *it;
				lbigsum -= *it;
				lbig.erase(it);
			}
			while (lsmall.size() > lbig.size()) {
				auto it = lsmall.end(); it--;
				lbig.insert(*it);
				lbigsum += *it;
				lsmallsum -= *it;
				lsmall.erase(it);
			}
			//calc left median
			it = lsmall.end(); it--;
			lmed = *it;
			//~ cout << "L DONE" << endl;
			//calc left sum
			tmp += abs(lbigsum-lsmallsum);
			//~ cout << lmed << ": " << tmp;
			//calc right sum
			tmp += abs(rbigsum-rsmallsum);
			//update ans
			res = min(res, tmp);
			//~ cout << " AAA " << rmed << ": " << tmp << endl;
		}
		cout << res+ans << endl;
	}
}

//change if to while if wa as may be multiple??
//changes infinities higher if wa

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:45:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < all.size(); i++) {
      |                   ~~^~~~~~~~~~~~
bridge.cpp:46:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    if (i <= all.size()/2) {
      |        ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 544 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 16 ms 5464 KB Output is correct
13 Correct 33 ms 6992 KB Output is correct
14 Correct 25 ms 5720 KB Output is correct
15 Correct 18 ms 4188 KB Output is correct
16 Correct 22 ms 6044 KB Output is correct
17 Correct 23 ms 6740 KB Output is correct
18 Correct 27 ms 6228 KB Output is correct
19 Correct 32 ms 6732 KB Output is correct
20 Correct 22 ms 6228 KB Output is correct
21 Correct 27 ms 6480 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -