Submission #60616

#	Time	Username	Problem	Language	Result	Execution time	Memory
60616		dukati8	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	490 ms	14512 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
vector <pair<long long,long long> > travels;
vector <long long> points;
long long cost(long long point){
  long long ans=0;
  for (auto a:travels) {
    long long c,d;
    c=a.first;
    d=a.second;
    ans+=abs(point-c) + abs(point-d);
  }
  return ans;
}
long long cost (long long point1, long long point2) {
  long long ans=0;
  for (auto a:travels) {
    long long c,d;
    c=a.first;
    d=a.second;
    ans+=min(abs(point1-c) + abs(point1-d),abs(point2-c) + abs(point2-d));
  }
  return ans;
}

int main() {
  unordered_set<long long> unip;
  int k,n;
  cin >> k >> n;
  long long sum=0;
  rep(i,0,n) {
    char a,b;
    long long c,d;
    cin >> a >> c >> b >> d;
    if (a==b) {
      sum+=abs(c-d);
    }
    else {
      travels.push_back(make_pair(min(c,d),max(c,d)));
      sum+=1;
      unip.insert(c);
      unip.insert(d);
    }
  }
  for (auto x:unip) {
    points.push_back(x);
  }
  if (k==1) {
    sort(all(points));
    int lo,hi;
    lo=0;
    hi=points.size()-1;
    while (lo+2<hi) {
      int mid1=lo+(hi-lo)/3;
      int mid2=lo+(2*hi-2*lo)/3;
      long long val1,val2;
      val1=cost(points[mid1]);
      val2=cost(points[mid2]);
      if (val1<val2) hi=mid2;
      else lo=mid1;
    }
    long long best=1000000000000000;
    rep (i,lo,hi+1) {
      best=min(best,cost(points[i]));
    }
    if (best==1000000000000000) best=0;
    cout << best+sum << endl;
  }
  else {
    sort(all(points));
    //Hillclimb, two indicies: a and b, a<=b
    if (points.size()==0) {
      cout << sum << endl;
    }
    else {
      long long best=cost(points[0],points[0]);
      int besta,bestb;
      besta=0;
      bestb=0;
      int m=points.size();
      int stepsize=2*points.size()/3;
      while (stepsize>0) {
        int tempa,tempb;
        tempa=besta;
        tempb=bestb;
        rep(i,-1,2) {
          rep(j,-1,2) {
            int a,b;
            a=besta+i*stepsize;
            b=bestb+j*stepsize;
            if (a>b) continue;
            if (a<0 || b>=m) continue;
            long long currcost=cost(points[a],points[b]);
            if (currcost<best) {
              best=currcost;
              tempa=a;
              tempb=b;
            }
          }
        }
        besta=tempa;
        bestb=tempb;
        stepsize/=2;
      }

      cout << sum+best << endl;
    }
  }


}

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