Submission #797412

#	Time	Username	Problem	Language	Result	Execution time	Memory
797412		erray	Robots (IOI13_robots)	C++17	100 / 100	344 ms	29148 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>

using namespace std;

template<typename A, typename B> 
string to_string(pair<A, B>);

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return "'"s + c + "'";
}
string to_string(const char* c) {
  return to_string(string(c));
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template<size_t T> 
string to_string(bitset<T> bs) {
  return bs.to_string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<typename T>
string to_string(T v) {
  string res = "{";
  for (auto x : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(x);
  }
  res += "}";
  return res;  
}
template<typename A, typename B> 
string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename H, typename... T> 
void debug_out(H head, T... tail) {
  cerr << "  " << to_string(head);
  debug_out(tail...);
}

#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]", debug_out(__VA_ARGS__)
#else 
  #define debug(...) void(37)
#endif

template<typename T>
vector<T> reverse_fuck(T* x, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = x[i];
  }
  return res;
}
struct DSU { //add small to large if it gets TLE
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int x) {
    return link[x] = (x == link[x] ? x : get(link[x]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    return true;
  }
};
  

int putaway(int A, int B, int T, int fuck_X[], int fuck_Y[], int fuck_W[], int fuck_S[]) {
  auto X = reverse_fuck(fuck_X, A);
  auto Y = reverse_fuck(fuck_Y, B);
  auto W = reverse_fuck(fuck_W, T);
  auto S = reverse_fuck(fuck_S, T);
  sort(X.begin(), X.end());
  sort(Y.begin(), Y.end());
  debug(X, Y, W, S);
  vector<int> ord_X(T);
  vector<int> ord_Y(T);
  iota(ord_X.begin(), ord_X.end(), 0);
  iota(ord_Y.begin(), ord_Y.end(), 0);
  sort(ord_X.begin(), ord_X.end(), [&](int x, int y) {
    return W[x] < W[y];
  });
  sort(ord_Y.begin(), ord_Y.end(), [&](int x, int y) {
    return S[x] < S[y];
  });
  vector<int> match_X(T, -1);
  {
    int p = 0;
    for (auto i : ord_X) {
      while (p < A && X[p] <= W[i]) {
        ++p;
      }
      match_X[i] = p;
    }
  }
  vector<int> match_Y(T, -1);
  {
    int p = 0;
    for (auto i : ord_Y) {
      while (p < B && Y[p] <= S[i]) {
        ++p;
      }
      match_Y[i] = p;
    }
  }
  reverse(ord_Y.begin(), ord_Y.end());
  debug(match_X, match_Y);
  auto Check = [&](int size) {
    debug(size);
    DSU next(A + 1);
    vector<int> left(A + 1, size);
    vector<int> for_Y(B + 1, 0);
    for (auto i : ord_Y) {
      int g = next.get(match_X[i]);
      debug(match_X[i], g, left[g]);
      if (g == A) {
        for_Y[match_Y[i]] += 1;
      } else {
        if (--left[g] == 0) {
          debug(g + 1, g);
          next.unite(g + 1, g);
        }
      }
    }
    debug(for_Y);
    int use = 0;
    for (int i = 0; i < B; ++i) {
      use += for_Y[i];
      use = max(0, use - size);
    }
    use += for_Y[B];
    return use == 0;
  };
  
  int low = 1, high = T;
  while (low < high) {
    int mid = (low + high) >> 1;
    if (!Check(mid)) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }  
  return (Check(low) ? low : -1);
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10