Submission #1338790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338790		mrbet	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	344 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define pb push_back
#define fi first
#define se second
#define vi vector
#define all(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define bit(_x,_y) (((_x) >> (_y)) & 1)
#define file "A"

string yes[2] = {"NO\n","YES\n"};
const ld eps = ld(1e-7);
const ll inf = ll(1e16) + 1;
const ll mod = ll(1e9) + 7;

template<class X, class Y>
inline bool Min(X &x, const Y &y) {
  if(x > y) {
    x = y;
    return true;
  }
  return false;
}

template<class X, class Y>
inline bool Max(X &x, const Y &y) {
  if(x < y) {
    x = y;
    return true;
  }
  return false;
}

const int N = int(1e5) +5;

int n,k,s[N],t[N];
vector<int> b;
vector<pii> v;

void Mei () {
    cin>>k>>n;

    ll ans=0;
    forr(i,1,n) {
        char p,q;
        cin>>p>>s[i]>>q>>t[i];
        if (p==q) ans+=abs(s[i]-t[i]);
        else {
        v.pb({s[i],t[i]});
        b.pb(abs(s[i]-t[i]));
        }
    }
    if (b.size()==0) {
        cout<<ans;
        return;
    }

    sort(all(b));
    b.erase(unique(all(b)),b.end());

    int sz= b.size();
    if (k==1) {
        int med= b[sz/2];
        for(pii x: v) {
            ll S= x.fi;
            ll T= x.se;
            ans+= abs(S-med)+abs(T-med)+1;
        }
        cout<<ans;
    }
    else {
        int mid= b.size()/2;
        int q1= mid/2;
        int q3= (b.size()+mid+1)/2;
        //cout<<q1<<' '<<q3<<'\n';
        for(pii x: v) {
            ll S=x.fi;
            ll T=x.se;
            if (S>T) swap(S,T);
            ll best= abs(S-b[q1])+abs(T-b[q1])+1;
            best=min(best, 1LL*abs(S-b[q3])+abs(T-b[q3])+1);
            best=min(best, 1LL*abs(S-b[q1])+abs(T-b[q3])+(b[q3]-b[q1])+1);
            ans+=best;
        }
        cout<<ans;
    }
}

void precalc() {
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(7);

  if (fopen(file".inp","r")) {
    freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  }
  else if (fopen(file".in","r")) {
    freopen(file".in","r",stdin); freopen(file".out","w",stdout);
  }

  int tc = 1;
 // cin >> tc;
  precalc();
  while(tc--) {
    Mei();
  }

  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:106:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     freopen(file".in","r",stdin); freopen(file".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:109:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     freopen(file".in","r",stdin); freopen(file".out","w",stdout);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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