Submission #74292

#	Time	Username	Problem	Language	Result	Execution time	Memory
74292		funcsr	Wiring (IOI17_wiring)	C++17	0 / 100	6 ms	5240 KiB

wiring

#include "wiring.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pb push_back
//#define INF (1LL<<60)
#define INF 1145141919
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
inline void chmin(long long &x, long long v) { if(x>v)x=v; }

int N;
vector<int> G[200000];
int pos[200000];
bool used[200000];

long long min_total_length(vector<int> A, vector<int> B) {
  rep(i, A.size()) {
    auto it = lower_bound(all(B), A[i]);
    int left = -1, right = -1;
    if (it != B.end()) right = it-B.begin();
    if (it != B.begin()) left = it-B.begin()-1;
    int l = left==-1?INF:abs(B[left]-A[i]);
    int r = right==-1?INF:abs(B[right]-A[i]);

    if (l <= r) G[i].pb(A.size()+left);
    if (r <= l) G[i].pb(A.size()+right);
  }
  rep(i, B.size()) {
    auto it = lower_bound(all(A), B[i]);
    int left = -1, right = -1;
    if (it != A.end()) right = it-A.begin();
    if (it != A.begin()) left = it-A.begin()-1;
    int l = left==-1?INF:abs(A[left]-B[i]);
    int r = right==-1?INF:abs(A[right]-B[i]);

    if (l <= r) G[i+A.size()].pb(left);
    if (r <= l) G[i+A.size()].pb(right);
  }
  rep(i, A.size()) pos[i] = A[i];
  rep(i, B.size()) pos[i+A.size()] = B[i];

  long long s = 0;
  int N = A.size()+B.size();
  int all = N;
  rep(i, N) used[i] = false;
  while (all > 0) {
    rep(x, N) if (!used[x]) {
      vector<int> gs;
      for (int t : G[x]) if (!used[t]) gs.pb(t);
      if (gs.size() == 1) {
        //cout<<pos[x]<<"<->"<<pos[gs[0]]<<"\n";
        s += abs(pos[gs[0]]-pos[x]);
        used[gs[0]] = true;
        used[x] = true;
        all--;
        all--;
        x=-1;
      }
    }
    rep(x, N) if (!used[x]) {
      vector<int> gs;
      for (int t : G[x]) if (!used[t]) gs.pb(t);
      if (gs.size() == 0) {
        //cout<<pos[x]<<"->"<<pos[G[x][0]]<<"\n";
        s += abs(pos[G[x][0]]-pos[x]);
        used[x] = true;
        all--;
      }
    }
  }
  return s;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:9:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:27:3: note: in expansion of macro 'rep'
   rep(i, A.size()) {
   ^~~
wiring.cpp:9:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:38:3: note: in expansion of macro 'rep'
   rep(i, B.size()) {
   ^~~
wiring.cpp:9:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:49:3: note: in expansion of macro 'rep'
   rep(i, A.size()) pos[i] = A[i];
   ^~~
wiring.cpp:9:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:50:3: note: in expansion of macro 'rep'
   rep(i, B.size()) pos[i+A.size()] = B[i];
   ^~~

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