Submission #640421

#	Time	Username	Problem	Language	Result	Execution time	Memory
640421		ggoh	Wiring (IOI17_wiring)	C++14	0 / 100	1074 ms	6064 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;
  vector<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].push_back(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 i=0;i<m;i++)
    {
      if(sz(V[i])>1)
      {
        for(int k=0;k<sz(V[i]);k++)
        {
          if(V[i][k]==-1)continue;
          if(abs(r[V[i][k]]-b[st[i]])-abs(r[V[i][k]]-b[i])<mini)
          {
            mini=abs(r[V[i][k]]-b[st[i]])-abs(r[V[i][k]]-b[i]);
            minind=k;minV=i;
          }
        }
      }
    }
    V[st[i]].push_back(V[minV][minind]);
    V[minV][minind]=-1;
  }
  lint ans=0;
  for(int i=0;i<m;i++)
  {
    for(auto &k:V[i])
    {
      if(k!=-1)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