Submission #640427

#	Time	Username	Problem	Language	Result	Execution time	Memory
640427		ggoh	Wiring (IOI17_wiring)	C++14	0 / 100	1089 ms	7520 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
 
lint min_total_length(vector<int> r, vector<int> b) {
  if(sz(r)<sz(b))swap(r,b);
  int n=sz(r),m=sz(b);
  int minV,mini,minind;
  set<int>V[100002];
  for(int i=0;i<n;i++)
  {
    mini=1e9+1;
    minind=-1;
    for(int j=0;j<m;j++)
    {
      if(abs(r[i]-b[j])<mini)
      {
        mini=abs(r[i]-b[j]);
        minind=j;
      }
    }
    V[minind].insert(i);
  }
  int st[100002],sz=0;
  for(int i=0;i<m;i++)
  {
    if(!sz(V[i]))st[sz++]=i;
  }
  for(int i=0;i<sz;i++)
  {
    mini=1e9+1;
    minind=-1;
    minV=-1;
    for(int j=0;j<m;j++)
    {
      if(sz(V[j])>1)
      {
        for(auto &k:V[j])
        {
          if(abs(r[k]-b[st[i]])-abs(r[k]-b[i])<mini)
          {
            mini=abs(r[k]-b[st[i]])-abs(r[k]-b[j]);
            minind=k;minV=j;
          }
        }
      }
    }
    V[st[i]].insert(minind);
    V[minV].erase(minind);
  }
  lint ans=0;
  for(int i=0;i<m;i++)
  {
    for(auto &k:V[i])
    {
      ans+=abs(r[k]-b[i]);
    }
  }
	return ans;
}

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