Submission #4721478
Source Code Expand
// This is free and unencumbered software released into the public domain.
// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.
// In jurisdictions that recognize copyright laws, the author or authors
// of this software dedicate any and all copyright interest in the
// software to the public domain. We make this dedication for the benefit
// of the public at large and to the detriment of our heirs and
// successors. We intend this dedication to be an overt act of
// relinquishment in perpetuity of all present and future rights to this
// software under copyright law.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
// For more information, please refer to <http://unlicense.org>
/****************/
/* template.hpp */
/****************/
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
using std::abs;
using std::cerr;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::numeric_limits;
using std::swap;
struct BoolName : std::numpunct<char> {
std::string t, f;
BoolName (std::string t, std::string f) : t(t), f(f) {}
std::string do_truename() const {return t;}
std::string do_falsename() const {return f;}
};
void set_bool_name(std::string t, std::string f) {
cout.imbue(std::locale(cout.getloc(), new BoolName(t, f)));
}
struct Initializer {
Initializer() {
cout << std::fixed << std::setprecision(15) << std::boolalpha;
set_bool_name("Yes", "No");
}
} initializer;
struct Input {
bool eof;
Input() : eof(false) {}
operator char() {
char v;
this->eof = (std::scanf("%c", &v) != 1);
return v;
}
operator int() {
int v;
this->eof = (std::scanf("%d", &v) != 1);
return v;
}
operator long() {
long v;
this->eof = (std::scanf("%ld", &v) != 1);
return v;
}
operator long long() {
long long v;
this->eof = (std::scanf("%lld", &v) != 1);
return v;
}
operator unsigned int() {
unsigned int v;
this->eof = (std::scanf("%u", &v) != 1);
return v;
}
operator unsigned long() {
unsigned long v;
this->eof = (std::scanf("%lu", &v) != 1);
return v;
}
operator unsigned long long() {
unsigned long long v;
this->eof = (std::scanf("%llu", &v) != 1);
return v;
}
operator double() {
double v;
this->eof = (std::scanf("%lf", &v) != 1);
return v;
}
operator long double() {
long double v;
this->eof = (std::scanf("%Lf", &v) != 1);
return v;
}
void ignore() const {
getchar();
}
} in;
template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}
template<typename T, typename S> std::function<S(T)> cast() {
return [](const T& t) { return static_cast<S>(t); };
}
/******************/
/* arithmetic.hpp */
/******************/
template<typename T> class Addition {
public:
template<typename V> T operator+(const V& v) const {
return T(static_cast<const T&>(*this)) += v;
}
T operator++() {
return static_cast<T&>(*this) += 1;
}
};
template<typename T> class Subtraction {
public:
template<typename V> T operator-(const V& v) const {
return T(static_cast<const T&>(*this)) -= v;
}
};
template<typename T> class Multiplication {
public:
template<typename V> T operator*(const V& v) const {
return T(static_cast<const T&>(*this)) *= v;
}
};
template<typename T> class Division {
public:
template<typename V> T operator/(const V& v) const {
return T(static_cast<const T&>(*this)) /= v;
}
};
template<typename T> class Modulus {
public:
template<typename V> T operator%(const V& v) const {
return T(static_cast<const T&>(*this)) %= v;
}
};
template<typename T> class IndivisibleArithmetic : public Addition<T>, public Subtraction<T>, public Multiplication<T> {};
template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public Division<T> {};
/*****************/
/* container.hpp */
/*****************/
#include <algorithm>
#include <vector>
template<typename T> class Container : public T {
private:
using S = typename T::value_type;
public:
Container() : T() {}
Container(int n) : T(n) {}
Container(int n, S s) : T(n, s) {}
template<typename Itr> Container(Itr first, Itr last) : T(first, last) {}
Container(const std::initializer_list<S>& v) : T(v) {}
Container(int n, Input& in) {
std::vector<S> v(n);
for (auto& i : v) {
i = in;
}
*this = Container<T>(v.begin(), v.end());
}
S max() const {
return *max_element(this->begin(), this->end());
}
template<typename Function> auto max(Function func) const {
std::vector<decltype(func(S()))> res;
std::transform(this->begin(), this->end(), std::back_inserter(res), func);
return *max_element(res.begin(), res.end());
}
S min() const {
return *min_element(this->begin(), this->end());
}
int argmax() const {
return max_element(this->begin(), this->end()) - this->begin();
}
int argmin() const {
return min_element(this->begin(), this->end()) - this->begin();
}
bool contains(const S& a) const {
return find(this->begin(), this->end(), a) != this->end();
}
int size() const { return T::size(); }
};
/***************/
/* ordered.hpp */
/***************/
template<typename T> class Ordered {
public:
template<typename V> bool operator==(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
}
template<typename V> bool operator!=(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
}
template<typename V> bool operator>(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this);
}
template<typename V> bool operator<=(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this));
}
template<typename V> bool operator>=(const V& v) const {
return !(static_cast<const T&>(*this) < static_cast<T>(v));
}
};
/**************/
/* vector.hpp */
/**************/
#include <numeric>
template<typename T> class Vector : public Container<std::vector<T>>, public Arithmetic<Vector<T>>, public Modulus<Vector<T>>, public Ordered<Vector<T>> {
public:
Vector() = default;
Vector(const Vector<T>& v) = default;
Vector(int n) : Container<std::vector<T>>(n) {}
Vector(int n, T t) : Container<std::vector<T>>(n, t) {}
template<typename Itr> Vector(Itr first, Itr last) : Container<std::vector<T>>(first, last) {}
Vector(const std::initializer_list<T>& v) : Container<std::vector<T>>(v) {}
Vector(int n, Input& in) : Container<std::vector<T>>(n, in) {}
Vector operator+=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] += v[i];
return *this;
}
Vector operator+=(const T& v) {
for (auto& i : *this) {
i += v;
}
return *this;
}
Vector operator-=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] -= v[i];
return *this;
}
Vector operator*=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] *= v[i];
return *this;
}
Vector operator/=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] /= v[i];
return *this;
}
Vector operator%=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] %= v[i];
return *this;
}
bool operator<(const Vector& v) const {
if (this->size() != v.size()) return this->size() < v.size();
for (int i = 0; i < this->size(); ++i) {
if ((*this)[i] != v[i]) {
return (*this)[i] < v[i];
}
}
return false;
}
T inner_product(const Vector<T>& v) const {
return std::inner_product(this->begin(), this->end(), v.begin(), T(0));
}
void output(std::string sep = "\n", std::string end = "\n") const {
if (!this->empty()) {
cout << (*this)[0];
}
for (int i = 1; i < this->size(); ++i) {
cout << sep << (*this)[i];
}
cout << end;
}
Vector<T> partial_sort(int k, bool reverse = false) {
if (!reverse) {
std::partial_sort(this->begin(), this->begin() + k, this->end());
} else {
std::partial_sort(this->begin(), this->begin() + k, this->end(), std::greater<T>());
}
return *this;
}
Vector<T> sort() {
std::sort(this->begin(), this->end());
return *this;
}
Vector<T> rsort() {
std::sort(this->rbegin(), this->rend());
return *this;
}
Vector<T> subvector(int a) const {
return Vector<T>(this->begin(), this->begin() + a);
}
Vector<T> subvector(int a, int b) const {
return Vector<T>(this->begin() + a, this->begin() + b);
}
template<typename Function> auto transform(Function func) const {
Vector<decltype(func(T()))> res;
std::transform(this->begin(), this->end(), std::back_inserter(res), func);
return res;
}
Vector<T> partial_sum() const {
Vector<T> res;
std::partial_sum(this->begin(), this->end(), std::back_inserter(res));
return res;
}
Vector<T> reverse() {
std::reverse(this->begin(), this->end());
return *this;
}
template<typename Function> bool all_of(Function func) {
return std::all_of(this->begin(), this->end(), func);
}
Vector<T> adjacent_difference() const {
Vector<T> res;
std::adjacent_difference(this->begin(), this->end(), std::back_inserter(res));
return res;
}
T lower_bound(T t) const {
return std::lower_bound(this->begin(), this->end(), t) - this->begin();
}
T accumulate() const {
return std::accumulate(this->begin(), this->end(), T(0));
}
template<typename S, typename Function> S accumulate(S n, Function func) const {
return std::accumulate(this->begin(), this->end(), n, func);
}
template<typename Int> static Vector<T> makeVector(Int n) {
return Vector<T>(n);
}
template<typename Int> static Vector<T> makeVector(Input& in, Int n) {
return Vector<T>(n, in);
}
template<typename Int, typename... Ints> static auto makeVector(Input& in, Int n, Ints... ints) {
Vector<decltype(makeVector(in, ints...))> res;
for (int i = 0; i < n; ++i) {
res.emplace_back(makeVector(in, ints...));
}
return res;
}
template<typename Int, typename... Ints> static auto makeVector(Int n, Ints... ints) {
Vector<decltype(makeVector(ints...))> res;
for (int i = 0; i < n; ++i) {
res.emplace_back(makeVector(ints...));
}
return res;
}
Vector<T> unique() {
this->erase(std::unique(this->begin(), this->end()), this->end());
return *this;
}
};
template<typename T> Vector<T> iota(int n, T m = 0) {
Vector<T> v(n);
std::iota(v.begin(), v.end(), m);
return v;
}
/*******************/
/* graph/graph.hpp */
/*******************/
struct Edge {
using CostType = int;
const static int cost = 1;
int to;
Edge(int to = -1) : to(to) {}
Edge(Input &in) : to(in) {}
bool isNone() const {return to == -1;}
operator int() const {return to;}
};
std::ostream& operator<<(std::ostream& s, const Edge& edge) {
s << edge.to;
return s;
}
template<typename Cost> struct WeightedEdge : public Edge {
using CostType = Cost;
Cost cost;
WeightedEdge(int to = -1, Cost cost = 0) : Edge(to), cost(cost) {}
WeightedEdge(Input &in) : Edge(in), cost(in) {}
};
template<typename Cost> std::ostream& operator<<(std::ostream& s, const WeightedEdge<Cost>& edge) {
s << edge.to << ',' << edge.cost;
return s;
}
template<typename Capacity> struct ResidualEdge : public Edge {
using CapacityType = Capacity;
Capacity cap;
int rev;
ResidualEdge(int to = -1, Capacity cap = 0) : Edge(to), cap(cap) {}
ResidualEdge(Input &in) {
Edge edge(in);
Capacity cap(in);
*this = ResidualEdge(edge, cap);
}
ResidualEdge reverse(int from) const {return ResidualEdge(from, 0);}
};
template<typename Capacity, typename Cost> struct WeightedResidualEdge : public ResidualEdge<Capacity> {
Cost cost;
WeightedResidualEdge(int to = -1, Capacity cap = 0, Cost cost = 0) : ResidualEdge<Capacity>(to, cap), cost(cost) {}
WeightedResidualEdge(Input &in) {
ResidualEdge<Capacity> edge(in);
Cost cost(in);
*this = WeightedResidualEdge(edge, cost);
}
WeightedResidualEdge reverse(int from) const {return WeightedResidualEdge(from, 0, -cost);}
};
template<typename Edge> struct FullEdge : public Edge {
int from;
FullEdge() = default;
FullEdge(const int from, const Edge& edge) : Edge(edge), from(from) {}
FullEdge(Input &in) {
int from(in);
Edge edge(in);
*this = FullEdge(from, edge);
}
};
template<typename Edge> std::ostream& operator<<(std::ostream& s, const FullEdge<Edge>& edge) {
s << '(' << edge.from << ',' << Edge(edge) << ')';
return s;
}
template<typename Edge> class Graph {
public:
using EdgeType = Edge;
virtual int size() const = 0;
template<typename... Args> void addEdge(int from, int to, Args...) {
(void)from;
(void)to;
}
template<typename... Args> void addUndirectedEdge(int from, int to, Args...) {
(void)from;
(void)to;
}
Vector<FullEdge<Edge>> getAllEdges() const {
Vector<FullEdge<Edge>> res;
for (int i = 0; i < size(); ++i) {
for (const auto& edge : getEdges(i)) {
res.emplace_back(i, edge);
}
}
return res;
}
virtual Vector<Edge> getEdges(int from) const = 0;
virtual Edge getEdge(int from, int to) const = 0;
virtual bool hasEdge(int from, int to) const = 0;
int getDegree(int v) const {
return getEdges(v).size();
}
Vector<int> getIndegree() const {
Vector<int> degree(size());
for (const auto& edge : getAllEdges()) ++degree[edge.to];
return degree;
}
};
template<typename Graph> Graph readGraph(Input &in, int n, int m, bool undirected, bool one_origin) {
Graph graph(n);
for (int i = 0; i < m; ++i) {
FullEdge<typename Graph::EdgeType> edge(in);
if (one_origin) {
--edge.from;
--edge.to;
}
if (undirected) graph.addUndirectedEdge(edge);
else graph.addEdge(edge);
}
return graph;
}
/****************************/
/* graph/adjacency_list.hpp */
/****************************/
template<typename Edge> class AdjacencyList : public Graph<Edge> {
protected:
Vector<Vector<Edge>> graph;
public:
using EdgeType = Edge;
AdjacencyList() = default;
AdjacencyList(int n) : graph(n) {}
AdjacencyList(Input &in, int n, int m, bool undirected = true, bool one_origin = true) {
*this = readGraph<AdjacencyList<Edge>>(in, n, m, undirected, one_origin);
}
int size() const {
return graph.size();
}
template<typename... Args> void addEdge(int from, int to, Args... args) {
graph[from].emplace_back(to, args...);
}
void addEdge(const FullEdge<Edge>& edge) {
graph[edge.from].emplace_back(edge);
}
template<typename... Args> void addUndirectedEdge(int from, int to, Args... args) {
addEdge(from, to, args...);
addEdge(to, from, args...);
}
void addUndirectedEdge(FullEdge<Edge> edge) {
graph[edge.from].emplace_back(edge);
swap(edge.from, edge.to);
graph[edge.from].emplace_back(edge);
}
Vector<Edge> getEdges(int from) const {
return graph[from];
}
Edge getEdge(int from, int to) const {
Edge res;
for (const auto& edge : graph[from]) {
if (edge.to == to) res = edge;
}
return res;
}
bool hasEdge(int from, int to) const {
for (const auto& edge : graph[from]) {
if (edge.to == to) return true;
}
return false;
}
Vector<Edge>& operator[](int v) {
return graph[v];
}
const Vector<Edge>& operator[](int v) const {
return graph[v];
}
};
/********************************/
/* graph/bipartite_matching.hpp */
/********************************/
class BipartiteMatching {
private:
AdjacencyList<Edge> graph;
Vector<bool> used;
bool dfs(int v) {
used[v] = true;
for (const Edge& u : graph[v]) {
int w = match[u.to];
if (w < 0 || (!used[w] && dfs(w))) {
match[v] = u.to;
match[u.to] = v;
return true;
}
}
return false;
}
public:
Vector<int> match;
BipartiteMatching(const AdjacencyList<Edge>& graph) : graph(graph), used(graph.size()), match(graph.size(), -1) {}
int solve() {
int res = 0;
for (int i = 0; i < graph.size(); ++i) {
if (match[i] >= 0) continue;
fill(used.begin(), used.end(), false);
if (dfs(i)) ++res;
}
return res;
}
};
int bipartiteMatching(const AdjacencyList<Edge>& graph) {
BipartiteMatching bm(graph);
return bm.solve();
}
/************/
/* main.cpp */
/************/
int main() {
set_bool_name("yes", "no");
int t(in), n(in);
Vector<int> a(n, in);
int m(in);
Vector<int> b(m, in);
AdjacencyList<Edge> graph(n + m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i] <= b[j] && b[j] <= a[i] + t) {
graph.addEdge(i, j + n);
}
}
}
cout << (bipartiteMatching(graph) == m) << endl;
}
Submission Info
Submission Time |
|
Task |
C - おいしいたこ焼きの売り方 |
User |
not |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
17708 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
rand0.txt, rand1.txt, rand10.txt, rand11.txt, rand12.txt, rand13.txt, rand14.txt, rand15.txt, rand16.txt, rand17.txt, rand18.txt, rand19.txt, rand2.txt, rand20.txt, rand21.txt, rand22.txt, rand23.txt, rand24.txt, rand25.txt, rand26.txt, rand27.txt, rand28.txt, rand29.txt, rand3.txt, rand4.txt, rand5.txt, rand6.txt, rand7.txt, rand8.txt, rand9.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
Case Name |
Status |
Exec Time |
Memory |
rand0.txt |
AC |
1 ms |
256 KB |
rand1.txt |
AC |
1 ms |
256 KB |
rand10.txt |
AC |
1 ms |
256 KB |
rand11.txt |
AC |
1 ms |
256 KB |
rand12.txt |
AC |
1 ms |
256 KB |
rand13.txt |
AC |
1 ms |
256 KB |
rand14.txt |
AC |
1 ms |
256 KB |
rand15.txt |
AC |
1 ms |
256 KB |
rand16.txt |
AC |
1 ms |
256 KB |
rand17.txt |
AC |
1 ms |
256 KB |
rand18.txt |
AC |
1 ms |
256 KB |
rand19.txt |
AC |
1 ms |
256 KB |
rand2.txt |
AC |
1 ms |
256 KB |
rand20.txt |
AC |
1 ms |
256 KB |
rand21.txt |
AC |
1 ms |
256 KB |
rand22.txt |
AC |
1 ms |
256 KB |
rand23.txt |
AC |
1 ms |
256 KB |
rand24.txt |
AC |
1 ms |
256 KB |
rand25.txt |
AC |
1 ms |
256 KB |
rand26.txt |
AC |
1 ms |
256 KB |
rand27.txt |
AC |
1 ms |
256 KB |
rand28.txt |
AC |
1 ms |
256 KB |
rand29.txt |
AC |
1 ms |
256 KB |
rand3.txt |
AC |
1 ms |
256 KB |
rand4.txt |
AC |
1 ms |
256 KB |
rand5.txt |
AC |
1 ms |
256 KB |
rand6.txt |
AC |
1 ms |
256 KB |
rand7.txt |
AC |
1 ms |
256 KB |
rand8.txt |
AC |
1 ms |
256 KB |
rand9.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
s3.txt |
AC |
1 ms |
256 KB |
s4.txt |
AC |
1 ms |
256 KB |
s5.txt |
AC |
1 ms |
256 KB |