Submission #372407

#	Time	Username	Problem	Language	Result	Execution time	Memory
372407		gozonite	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	124 ms	5148 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<int, int> pi;
#define MOD 1000000007LL

struct Data {
    ll fi, si;
};
bool cmp(const Data& a, const Data& b) { return a.fi+a.si < b.fi+b.si; }

int K, N;
vector<Data> info;
int n;
multiset<ll> fl, fh, sl, sh;
ll fls = 0, fhs = 0, sls = 0, shs = 0;

void trans(ll x) {
    if (sl.find(x) != sl.end()) {
        sl.erase(sl.find(x)); sls -= x;
        if (sl.size()+1 < sh.size()) { auto it = sh.begin(); sls += *it; shs -= *it; sl.insert(*it); sh.erase(it); }
    } else if (sh.find(x) != sh.end()) {
        sh.erase(sh.find(x)); shs -= x;
        if (sh.size() < sl.size()) { auto it = sl.end(); it--; shs += *it; sls -= *it; sh.insert(*it); sl.erase(it); }
    }
    if (x >= *fh.begin()) {
        fh.insert(x); fhs += x;
        if (fl.size()+1 < fh.size()) { auto it = fh.begin(); fls += *it; fhs -= *it; fl.insert(*it); fh.erase(it); }
    } else {
        fl.insert(x); fls += x;
        if (fh.size() < fl.size()) { auto it = fl.end(); it--; fhs += *it; fls -= *it; fh.insert(*it); fl.erase(it); }
    }
}

int main() {
    //freopen("feast.in", "r", stdin);
    //freopen("feast.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    
    cin >> K >> N;
    
    ll pre = 0;
    for (int i = 0; i < N; i++) {
        char fc, sc; int fi, si;
        cin >> fc >> fi >> sc >> si;
        if (fc == sc) pre += abs(fi-si);
        else info.push_back({fi, si});
    }
    n = info.size();
    //cout << "pre: " << pre << endl;
    //cout << "info: ";
    //for (auto pp : info) cout << pp.fi << " " << pp.si << " | "; cout << endl;
    
    if (info.size() == 0) {
        cout << pre << endl;
        return 0;
    }
    
    if (K == 1) {
        vector<ll> v;
        for (auto pp : info) {
            v.push_back(pp.fi);
            v.push_back(pp.si);
        }
        sort(v.begin(), v.end());
        ll ans = info.size();
        for (int i = 0; i < v.size(); i++) ans += abs(v[i]-v[v.size()/2]);
        cout << ans+pre << endl;
        
        //cout << "Debugging v: " << v[v.size()/2] << endl;
        //for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << endl;
    } else if (K == 2) {
        sort(info.begin(), info.end(), cmp);
        
        vector<ll> v;
        for (auto pp : info) {
            v.push_back(pp.fi);
            v.push_back(pp.si);
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size()/2; i++) { sl.insert(v[i]); sls += v[i]; }
        for (int i = v.size()/2; i < v.size(); i++) { sh.insert(v[i]); shs += v[i]; }
        
        ll ans = 1e18;
        for (int i = 0; i < info.size()-1; i++) {
            trans(info[i].fi); trans(info[i].si);
            ll med = *fh.begin(), fs = ((ll)(fl.size())*med - fls) + (fhs - ((ll)fh.size())*med);
            med = *sh.begin(); ll ss = ((ll)(sl.size())*med - sls) + (shs - ((ll)sh.size())*med);
            ans = min(ans, fs+ss);
            
            cout << "Debugging: " << i << " " << fs << " " << ss << endl;
            for (auto pp : fl) cout << pp << " "; cout << ": " << fls << endl;
            for (auto pp : fh) cout << pp << " "; cout << ": " << fhs << endl;
            for (auto pp : sl) cout << pp << " "; cout << ": " << sls << endl;
            for (auto pp : sh) cout << pp << " "; cout << ": " << shs << endl;
        }
        
        ans += (ll)info.size();
        cout << ans+pre << endl;
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < v.size(); i++) ans += abs(v[i]-v[v.size()/2]);
      |                         ~~^~~~~~~~~~
bridge.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i = 0; i < v.size()/2; i++) { sl.insert(v[i]); sls += v[i]; }
      |                         ~~^~~~~~~~~~~~
bridge.cpp:86:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int i = v.size()/2; i < v.size(); i++) { sh.insert(v[i]); shs += v[i]; }
      |                                  ~~^~~~~~~~~~
bridge.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < info.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~~~~
bridge.cpp:96:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |             for (auto pp : fl) cout << pp << " "; cout << ": " << fls << endl;
      |             ^~~
bridge.cpp:96:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   96 |             for (auto pp : fl) cout << pp << " "; cout << ": " << fls << endl;
      |                                                   ^~~~
bridge.cpp:97:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |             for (auto pp : fh) cout << pp << " "; cout << ": " << fhs << endl;
      |             ^~~
bridge.cpp:97:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |             for (auto pp : fh) cout << pp << " "; cout << ": " << fhs << endl;
      |                                                   ^~~~
bridge.cpp:98:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   98 |             for (auto pp : sl) cout << pp << " "; cout << ": " << sls << endl;
      |             ^~~
bridge.cpp:98:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |             for (auto pp : sl) cout << pp << " "; cout << ": " << sls << endl;
      |                                                   ^~~~
bridge.cpp:99:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   99 |             for (auto pp : sh) cout << pp << " "; cout << ": " << shs << endl;
      |             ^~~
bridge.cpp:99:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |             for (auto pp : sh) cout << pp << " "; cout << ": " << shs << endl;
      |                                                   ^~~~

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