oj.uz

Submission #1083186

# Submission time Handle Problem Language Result Execution time Memory
1083186 2024-09-02T17:29:08 Z damamila Palembang Bridges (APIO15_bridge) C++14
22 / 100
 32 ms 6788 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 = n;
	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) {
			m--;
			ans += abs(b-a);
		} else {
			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 = 0;
		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
			if (rbig.size() > rsmall.size()) {
				auto it = rbig.begin();
				rsmall.insert(*it);
				rbigsum -= *it;
				rsmallsum += *it;
				rbig.erase(rbig.begin());
			} 
			if (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
			if (lbig.size() > lsmall.size()) {
				auto it = lbig.begin();
				lsmall.insert(*it);
				lsmallsum += *it;
				lbigsum -= *it;
				lbig.erase(it);
			}
			if (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) {
      |        ~~^~~~~~~~~~~~~~~
bridge.cpp:61:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |    auto [tot, a, b] = num[i];
      |         ^

Subtask #1
8.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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 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 1 ms 348 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 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 17 ms 5340 KB Output is correct
13 Correct 32 ms 6732 KB Output is correct
14 Correct 25 ms 5720 KB Output is correct
15 Correct 25 ms 4472 KB Output is correct
16 Correct 20 ms 5976 KB Output is correct
17 Correct 22 ms 6788 KB Output is correct
18 Correct 31 ms 6220 KB Output is correct
19 Correct 32 ms 6740 KB Output is correct
20 Correct 26 ms 6216 KB Output is correct
21 Correct 29 ms 6484 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 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 1 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 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -