#645139 (C++17) No.1467 Selling Cars

提出ソース
結果

問題	No.1467 Selling Cars
ユーザー	iaNTU
提出日時	2021-04-06 22:10:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	160 ms / 4,000 ms
コード長	16,885 bytes
コンパイル時間	2,378 ms
コンパイル使用メモリ	211,732 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-11 20:08:06
合計ジャッジ時間	5,242 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	160 ms 5,248 KB
testcase_01	AC	70 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	37 ms 5,376 KB
testcase_04	AC	41 ms 5,376 KB
testcase_05	AC	40 ms 5,376 KB
testcase_06	AC	39 ms 5,376 KB
testcase_07	AC	40 ms 5,376 KB
testcase_08	AC	38 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	25 ms 5,376 KB
testcase_12	AC	30 ms 5,376 KB
testcase_13	AC	29 ms 5,376 KB
testcase_14	AC	6 ms 5,376 KB
testcase_15	AC	9 ms 5,376 KB
testcase_16	AC	10 ms 5,376 KB
testcase_17	AC	25 ms 5,376 KB
testcase_18	AC	29 ms 5,376 KB
testcase_19	AC	138 ms 5,376 KB
testcase_20	AC	62 ms 5,376 KB
testcase_21	AC	46 ms 5,376 KB
testcase_22	AC	115 ms 5,376 KB
testcase_23	AC	76 ms 5,376 KB
testcase_24	AC	44 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	16 ms 5,376 KB
testcase_27	AC	16 ms 5,376 KB
testcase_28	AC	66 ms 5,376 KB
testcase_29	AC	7 ms 5,376 KB
testcase_30	AC	7 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	3 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// Exported by Exporter.exe

// Included from A.cpp
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
#define R Read
#define RD Read_Digit
#define RP Read_P
#define RL Read_Loop
#define RLD Read_Loop_Digit
#define RLP Read_Loop_P
#ifdef ONLINE_JUDGE
	#define Debug(x) ;
	#define Debugln(x) ;
	#define Debug_Array(n,x) ;
	#define Debugln_Array(n,x) ;
	#define NL ;
#else
	#define Debug(x) printf("%s :", (#x)); _Debug(x)
	#define Debugln(x) printf("%s :", (#x)); _Debugln(x)
	#define Debug_Array(n,x) printf("%s :", (#x)); _Debug_Array((n), (x))
	#define Debugln_Array(n,x) printf("%s :", (#x)); _Debugln_Array((n), (x))
	#define NL printf("\n")
#endif
typedef long long int ll;
typedef unsigned long long int ull;

constexpr int kN = int(2E3 + 10);
// constexpr int kMod = 998244353;
// constexpr int kMod = int(1E9 + 7);
// constexpr int kInf = 0x3f3f3f3f;
constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;
// constexpr double kPi = acos(-1);
// constexpr double kEps = 1E-9;


// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp
// --- Get ---
static inline char Get_Raw_Char() {
	static char buf[1 << 16], *p = buf, *end = buf;
	if (p == end) {
		if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
		p = buf;
	}
	return *p++;
}

// --- Read ---
template <typename T> static inline void Read_P(T &n) {
	static_assert(is_integral<T>::value);
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	return ;
}

template <typename T> static inline void Read(T &n) {
	static_assert(is_integral<T>::value);
	char c;
	bool neg = false;
	while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	if (neg) n = -n;
	return ;
}

template <typename T> static inline void Read_Digit(T &n) {
	static_assert(is_integral<T>::value);
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	n = int(c - '0');
	return ;
}

// --- Read multiple ---
template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read(n); return Read(Fargs...);}
template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {Read_Digit(n); return Read_Digit(Fargs...);}
template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P(n); return Read_P(Fargs...);}

// --- Read Loop ---
template <typename T> static inline void Read_Loop_i(int i, T *a) {return Read(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_i(int i, T *a, Targs*... Fargs) {Read(a[i]); return Read_Loop_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...);}

template <typename T> static inline void Read_Loop_Digit_i(int i, T *a) {return Read_Digit(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_Digit_i(int i, T *a, Targs*... Fargs) {Read_Digit(a[i]); return Read_Loop_Digit_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_Digit(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_Digit_i(i, Fargs...);}

template <typename T> static inline void Read_Loop_P_i(int i, T *a) {return Read_P(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_P_i(int i, T *a, Targs*... Fargs) {Read_P(a[i]); return Read_Loop_P_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_P(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_P_i(i, Fargs...);}

// --- Float ---
template <int mul, typename T> static inline void Read(T &n) {
	char c;
	bool neg = false;
	while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt++ < mul) n = n * 10;

	if (neg) n = -n;
	return ;
}

template <int mul, typename T> static inline void Read_P(T &n) {
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt++ < mul) n = n * 10;
	return ;
}

template <int mul, typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read<mul>(n); return Read<mul>(Fargs...);}
template <int mul, typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P<mul>(n); return Read_P<mul>(Fargs...);}

// --- init ---
inline void IOS() {ios::sync_with_stdio(false); cin.tie(0);}
inline void Freopen(const char *in, const char *out) {freopen(in, "r", stdin); freopen(out, "w", stdout);}

// --- Output ---
template <typename T> void Print(T x) {
	if (x < 0) {
		printf("-");
		x = -x;
	}
	if (x == 0) printf("0");
	else {
		static int val[100];
		int idx = -1;
		while (x) {
			val[++idx] = x % 10;
			x /= 10;
		}
		while (idx >= 0) printf("%d", val[idx--]);
	}
} 
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp


// Included from C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp
template <typename T> inline void sort(vector<T> &v) {return sort(v.begin(), v.end());}
template <typename T> inline void sort_r(vector<T> &v) {return sort(v.begin(), v.end(), greater<T>());}

template <typename T> inline void reverse(vector<T> &v) {return reverse(v.begin(), v.end());}

template <typename T> inline void Merge(vector<T> &a, vector<T> &b, vector<T> &c) {
	if (c.size() < a.size() + b.size()) c.resize(a.size() + b.size());
	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	return ;
}

template <typename T> inline void Discrete(vector<T> &v) {sort(v); v.resize(unique(v.begin(), v.end()) - v.begin());}

template <typename T> using PQ = priority_queue<T>;
template <typename T> using PQ_R = priority_queue<T, vector<T>, greater<T>>;

template <typename T> inline T ABS(T n) {return n >= 0 ? n : -n;}
template <typename T> inline T gcd(T a, T b) {return b ? gcd(b, a % b) : a;}
template <typename T> inline T lcm(T a, T b) {return a * b / gcd(a, b);}
template <typename T, typename... Targs> inline T min(T a, T b, T c, Targs... args) {return min(a, min(b, c, args...));}
template <typename T, typename... Targs> inline T max(T a, T b, T c, Targs... args) {return max(a, max(b, c, args...));}
template <typename T> inline void chmin(T &a, T b) {a = min(a, b); return ;}
template <typename T> inline void chmax(T &a, T b) {a = max(a, b); return ;}
template <typename T, typename... Targs> inline void chmin(T &a, T b, T c, Targs... args) {a = min(a, min(b, c, args...)); return ;}
template <typename T, typename... Targs> inline void chmax(T &a, T b, T c, Targs... args) {a = max(a, max(b, c, args...)); return ;}

template <typename T> inline int Digit_Sum(T a) {
	int ans = 0;
	while (a) {
		ans += a % 10;
		a /= 10;
	}
	return ans;
}
template <typename T> inline int Num_Length(T a) {
	int ans = 1;
	while (a /= 10) ans++;
	return ans;
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp


// Included from C:\Users\ianli\Desktop\CP\template\Various\Debug\Debug.cpp
void _print(int x) {printf("%d", x);}
void _print(long long int x) {printf("%lld", x);}
void _print(double x) {printf("%lf", x);}
template <typename T> void _print(T x) {return x.out();}
template <typename T1, typename T2> void _print(pair<T1, T2> x) {printf("("); _print(x.first); printf(", "); _print(x.second); printf(")");}

template <typename T> void _Debug(T x) {_print(x); printf("\n");}
template <typename T> void _Debug(vector<T> v) {
	if (v.empty()) printf(" empty");
	else for (T i : v) printf(" "), _print(i); 
	printf("\n");
}

template <typename T1, typename T2, typename T3> void _Debug(priority_queue<T1, T2, T3> pq) {
	if (pq.empty()) printf(" empty");
	else {
		while (!pq.empty()) {
			printf(" ");
			_print(pq.top());
			pq.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(queue<T> q) {
	if (q.empty()) printf(" empty");
	else {
		while (!q.empty()) {
			printf(" ");
			_print(q.front());
			q.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(stack<T> st) {
	if (st.empty()) printf(" empty");
	else {
		while (!st.empty()) {
			printf(" ");
			_print(st.top());
			st.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(deque<T> dq) {
	if (dq.empty()) printf(" empty");
	else {
		while (!dq.empty()) {
			printf(" ");
			_print(dq.front());
			dq.pop_front();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(vector<T> v) {
	if (v.empty()) printf(" empty\n");
	else {
		for (T i : v) printf("\n"), _print(i); 
		printf("\n");
	}
}

template <typename T1, typename T2, typename T3> void _Debugln(priority_queue<T1, T2, T3> pq) {
	if (pq.empty()) printf(" empty");
	else {
		while (!pq.empty()) {
			printf("\n");
			_print(pq.top());
			pq.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(queue<T> q) {
	if (q.empty()) printf(" empty");
	else {
		while (!q.empty()) {
			printf("\n");
			_print(q.front());
			q.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(stack<T> st) {
	if (st.empty()) printf(" empty");
	else {
		while (!st.empty()) {
			printf("\n");
			_print(st.top());
			st.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(deque<T> dq) {
	if (dq.empty()) printf(" empty");
	else {
		while (!dq.empty()) {
			printf("\n");
			_print(dq.front());
			dq.pop_front();
		}
	}
	printf("\n");
}

template <typename T> void _Debug_Array(int n, const T *x) {for (int i = 1; i <= n; i++) printf(" "), _print(x[i]); printf("\n");}
template <typename T> void _Debugln_Array(int n, const T *x) {printf("\n"); for (int i = 1; i <= n; i++) _print(x[i]), printf("\n");}
// End of C:\Users\ianli\Desktop\CP\template\Various\Debug\Debug.cpp


// Included from C:\Users\ianli\Desktop\CP\template\Flow\MCMF\Atcoder.cpp
namespace atcoder {
	namespace internal {
		template <class E> struct csr {
			std::vector<int> start;
			std::vector<E> elist;
			explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {
			for (auto e : edges) start[e.first + 1]++;
			for (int i = 1; i <= n; i++) start[i] += start[i - 1];
			auto counter = start;
			for (auto e : edges) elist[counter[e.first]++] = e.second;
			}
		};
	}

	template <class Cap, class Cost> struct MCMF {
		public:
			MCMF() {}
			explicit MCMF(int n) : _n(n) {}

			void init(int n) {_n = n; return _edges.clear();}
			void AddEdge(int from, int to, Cap cap, Cost cost) {return _edges.push_back(Edge(from, to, cap, cost));}

			struct Edge {
				int from, to;
				Cap cap, flow;
				Cost cost;
				Edge(int a, int b, Cap f, Cost c) : from(a), to(b), cap(f), flow(0), cost(c) {}
			};

			Edge GetEdge(int i) const {return _edges[i];}
			std::vector<Edge> Edges() const {return _edges;}

			std::pair<Cap, Cost> flow(int s, int t) {return flow(s, t, std::numeric_limits<Cap>::max());}
			std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {return slope(s, t, flow_limit).back();}
			std::vector<std::pair<Cap, Cost>> slope(int s, int t) {return slope(s, t, std::numeric_limits<Cap>::max());}
			std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
				int m = int(_edges.size());
				std::vector<int> edge_idx(m);

				auto g = [&]() {
					std::vector<int> degree(_n), redge_idx(m);
					std::vector<std::pair<int, _Edge>> elist;
					elist.reserve(m << 1);
					for (int i = 0; i < m; i++) {
						auto e = _edges[i];
						edge_idx[i] = degree[e.from]++;
						redge_idx[i] = degree[e.to]++;
						elist.push_back(make_pair(e.from, _Edge(e.to, -1, e.cap - e.flow, e.cost)));
						elist.push_back(make_pair(e.to, _Edge(e.from, -1, e.flow, -e.cost)));
					}
					auto _g = internal::csr<_Edge>(_n, elist);
					for (int i = 0; i < m; i++) {
						auto e = _edges[i];
						edge_idx[i] += _g.start[e.from];
						redge_idx[i] += _g.start[e.to];
						_g.elist[edge_idx[i]].rev = redge_idx[i];
						_g.elist[redge_idx[i]].rev = edge_idx[i];
					}
					return _g;
				}();

				auto result = slope(g, s, t, flow_limit);
				
				for (int i = 0; i < m; i++) _edges[i].flow = _edges[i].cap - g.elist[edge_idx[i]].cap;
				return result;
			}

		private:
			int _n;
			std::vector<Edge> _edges;

			struct _Edge {
				int to, rev;
				Cap cap;
				Cost cost;
				_Edge() {}
				_Edge(int a, int b, Cap f, Cost c): to(a), rev(b), cap(f), cost(c) {}
			};

			std::vector<std::pair<Cap, Cost>> slope(internal::csr<_Edge>& g, int s, int t, Cap flow_limit) {
				std::vector<std::pair<Cost, Cost>> dual_dist(_n);
				std::vector<int> prev_e(_n);
				std::vector<bool> vis(_n);
				struct Q {
					Cost key;
					int to;
					Q(Cost a, int b): key(a), to(b) {}
					bool operator < (Q r) const {return key > r.key;}
				};
				std::vector<int> que_min;
				std::vector<Q> que;
				auto dual_ref = [&]() {
					for (int i = 0; i < _n; i++) dual_dist[i].second = std::numeric_limits<Cost>::max();
					std::fill(vis.begin(), vis.end(), false);
					que_min.clear();
					que.clear();

					size_t heap_r = 0;

					dual_dist[s].second = 0;
					que_min.push_back(s);
					while (!que_min.empty() || !que.empty()) {
						int v;
						if (!que_min.empty()) {
							v = que_min.back();
							que_min.pop_back();
						}
						else {
							while (heap_r < que.size()) {
								heap_r++;
								std::push_heap(que.begin(), que.begin() + heap_r);
							}
							v = que.front().to;
							std::pop_heap(que.begin(), que.end());
							que.pop_back();
							heap_r--;
						}
						if (vis[v]) continue;
						vis[v] = true;
						if (v == t) break;
						Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
						for (int i = g.start[v]; i < g.start[v + 1]; i++) {
							auto e = g.elist[i];
							if (!e.cap) continue;
							Cost cost = e.cost - dual_dist[e.to].first + dual_v;
							if (dual_dist[e.to].second - dist_v > cost) {
								Cost dist_to = dist_v + cost;
								dual_dist[e.to].second = dist_to;
								prev_e[e.to] = e.rev;
								if (dist_to == dist_v) que_min.push_back(e.to);
								else que.push_back(Q(dist_to, e.to));
							}
						}
					}
					if (!vis[t]) return false;

					for (int v = 0; v < _n; v++) if (vis[v]) dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
					return true;
				};
				Cap flow = 0;
				Cost cost = 0, prev_cost_per_flow = -1;
				std::vector<std::pair<Cap, Cost>> result = {make_pair(Cap(0), Cost(0))};
				while (flow < flow_limit) {
					if (!dual_ref()) break;
					Cap c = flow_limit - flow;
					for (int v = t; v != s; v = g.elist[prev_e[v]].to) c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
					for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
						auto &e = g.elist[prev_e[v]];
						e.cap += c;
						g.elist[e.rev].cap -= c;
					}
					Cost d = -dual_dist[s].first;
					flow += c;
					cost += c * d;
					if (prev_cost_per_flow == d) result.pop_back();
					result.push_back(make_pair(flow, cost));
					prev_cost_per_flow = d;
				}
				return result;
			}
	};
}

// End of C:\Users\ianli\Desktop\CP\template\Flow\MCMF\Atcoder.cpp

using namespace atcoder;

int a[kN], b[kN];
ll ans[kN];
deque<int> dq[kN];
int to[kN], closest[kN];

int main() {
	int m, n; RP(m, n);
	RLP(m, a);
	RLP(n, b);

	sort(a + 1, a + m + 1);
	sort(b + 1, b + n + 1);

	for (int i = 1, j = 1; i <= m; i++) {
		while (j < n && ABS(a[i] - b[j]) > ABS(a[i] - b[j + 1])) j++;
		closest[i] = j;
	}

	for (int k = 1; k <= m; k++) {

		for (int i = 1; i <= n; i++) dq[i].clear();
		for (int i = 1; i <= m; i++) {
			if (int(dq[closest[i]].size()) < k) {
				to[i] = closest[i];
				dq[closest[i]].PB(i);
			}
			else {
				int l = closest[i] - 1, r = closest[i] + 1;
				while (l >= 1 && int(dq[l].size()) == k) l--;
				while (r <= n && int(dq[r].size()) == k) r++;

				ll ta = 0, tb = kInf;
				if (r <= n) chmin(tb, ABS<ll>(a[i] - b[r]));
				if (l == 0) ta = kInf;
				else {
					for (int j = l + 1; j < r; j++) ta += ABS(a[dq[j].front()] - b[j - 1]) - ABS(a[dq[j].front()] - b[j]);
					ta += ABS(a[i] - b[r - 1]);
				}

				if (tb <= ta) {
					dq[r].PB(i);
					to[i] = r;
				}
				else {
					for (int j = l + 1; j < r; j++) {
						to[dq[j].front()] = j - 1;
						dq[j - 1].PB(dq[j].front());
						dq[j].pop_front();
					}
					to[i] = r - 1;
					dq[r - 1].PB(i);
				}
			}
		}

		//Debug_Array(m, to);

		for (int i = 1; i <= m; i++) ans[k] += ABS(a[i] - b[to[i]]);
	}

	for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}
// End of A.cpp
yukicoder

結果

テストケース

ソースコード
