제출 #781213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781213		GusterGoose27	전선 연결 (IOI17_wiring)	C++17	0 / 100	450 ms	98212 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5+5;
const ll inf = 1e18;
set<pii> pairs;
map<ll, ll> dp;
int n;

int _abs(int v) {
	return v < 0 ? -v : v;
}

ll hsh(int i, int j, bool lmatch, bool rmatch) {
	return (ll) 4*i*n+4*j+2*lmatch+rmatch;
}

ll make_dp(int i, int j, bool lmatch, bool rmatch, vector<int> &r, vector<int> &b) {
	int cost = _abs(r[i]-b[j]);
	if (i == r.size()-1 && j == b.size()-1) {
		return cost;
	}
	ll cur_hsh = hsh(i, j, lmatch, rmatch);
	if (dp.find(cur_hsh) != dp.end()) return dp[cur_hsh];
	ll ans = inf;
	if (pairs.find(pii(i+1, j)) != pairs.end()) {
		if (lmatch) ans = min(ans, make_dp(i+1, j, 0, rmatch, r, b));
		ans = min(ans, make_dp(i+1, j, 0, 1, r, b)+cost);
	}
	if (pairs.find(pii(i, j+1)) != pairs.end()) {
		if (rmatch) ans = min(ans, make_dp(i, j+1, lmatch, 0, r, b));;
		ans = min(ans, make_dp(i, j+1, 1, 0, r, b)+cost);
	}
	dp[cur_hsh] = ans;
	// cerr << i << ' ' << j << ' ' << lmatch << ' ' << rmatch << ' ' << ans << '\n';
	return ans;
}

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size()+b.size();
	int i = 0;
	for (int j = 0; j < b.size(); j++) {
		while (i < r.size() && r[i] < b[j]) i++;
		if (i < r.size()) pairs.insert(pii(i, j));
		if (i) pairs.insert(pii(i-1, j));
	}
	int j = 0;
	for (int i = 0; i < r.size(); i++) {
		while (j < b.size() && b[j] < r[i]) j++;
		if (j < b.size()) pairs.insert(pii(i, j));
		if (j) pairs.insert(pii(i, j-1));
	}
	return make_dp(0, 0, 0, 0, r, b);
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'll make_dp(int, int, bool, bool, std::vector<int>&, std::vector<int>&)':
wiring.cpp:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if (i == r.size()-1 && j == b.size()-1) {
      |      ~~^~~~~~~~~~~~~
wiring.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if (i == r.size()-1 && j == b.size()-1) {
      |                         ~~^~~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int j = 0; j < b.size(); j++) {
      |                  ~~^~~~~~~~~~
wiring.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (i < r.size() && r[i] < b[j]) i++;
      |          ~~^~~~~~~~~~
wiring.cpp:50:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if (i < r.size()) pairs.insert(pii(i, j));
      |       ~~^~~~~~~~~~
wiring.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < r.size(); i++) {
      |                  ~~^~~~~~~~~~
wiring.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (j < b.size() && b[j] < r[i]) j++;
      |          ~~^~~~~~~~~~
wiring.cpp:56:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   if (j < b.size()) pairs.insert(pii(i, j));
      |       ~~^~~~~~~~~~

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