Submission #801809

#	Time	Username	Problem	Language	Result	Execution time	Memory
801809		kirakaminski968	Wiring (IOI17_wiring)	C++17	100 / 100	94 ms	31216 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int INF = 1234567890;
int n;
pair<int,int> arr[1000005];
set<int> sa, sb;
int getnearest(int x){
  int res = 2e9; 
  if(arr[x].second == 1){
    auto p = sa.lower_bound(arr[x].first); 
    if(p != sa.end()){
      res = min(res,*p-arr[x].first); 
    }
    if(p != sa.begin()){
      p--; 
      res = min(res,arr[x].first-*p); 
    }
  }
  else{
    auto p = sb.lower_bound(arr[x].first); 
    if(p != sb.end()){
      res = min(res,*p-arr[x].first); 
    }
    if(p != sb.begin()){
      p--; 
      res = min(res,arr[x].first-*p); 
    }
  }
  return res; 
}
ll prefa[1000005], prefb[1000005];
ll dp[1000005];
int mat[1000005], prv[2000005];
long long min_total_length(vector<int> aa, vector<int> bb) {
  int p = aa.size();
  int q = bb.size();
  for(int i = 1;i<=p;++i){
    arr[i].first = aa[i-1]; arr[i].second = -1; 
    sa.insert(aa[i-1]); 
  }
  for(int i = 1;i<=q;++i){
    arr[i+p].first = bb[i-1]; arr[i+p].second = 1; 
    sb.insert(bb[i-1]); 
  }
  n = p+q;
  sort(arr+1, arr+n+1);
  memset(mat, -1, sizeof(mat));
  memset(prv, -1, sizeof(prv));
  prv[n] = 0;
  int cur = n;
  for(int i = 1;i<=n;++i){
    prefa[i] = prefa[i-1]; prefb[i] = prefb[i-1]; 
    if(arr[i].second == -1){
      prefa[i] += arr[i].first; 
      cur++; 
    }
    else{
      prefb[i] += arr[i].first; 
      cur--; 
    }
    if(prv[cur] >= 0) mat[i] = prv[cur]; 
    prv[cur] = i; 
  }
  for(int i = 1;i<=n;++i){
    dp[i] = dp[i-1]+getnearest(i); 
    if(~mat[i]){
      dp[i] = min(dp[i],dp[mat[i]] + abs(prefa[i]-prefa[mat[i]]-prefb[i]+prefb[mat[i]])); 
    }
  }
  return dp[n];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45