제출 #895700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895700		joonwu04	전선 연결 (IOI17_wiring)	C++17	10 / 100	116 ms	8532 KiB

wiring

#include "wiring.h" 
#include <iostream>
#define MAX 1000000000000000000

using namespace std;

typedef long long ll;

ll abs(ll x) {
	return x>=0 ? x:-x;
}

bool isSub1(int rSize, int bSize) {
	return rSize<=200 && bSize<=200;
}

ll sub1Dp[210][210]; // sub1Dp[i][j]: minCost when connecting r[0~i], b[0~j]

ll sub1(vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	
	sub1Dp[0][0] = abs(r[0] - b[0]);
	for(int j=1; j<m; j++) {
		sub1Dp[0][j] = sub1Dp[0][j-1] + abs(r[0] - b[j]);
	}
	for(int i=1; i<n; i++) {
		sub1Dp[i][0] = sub1Dp[i-1][0] + abs(r[i] - b[0]);
		for(int j=1; j<m; j++) {
			// r[i], b[j] should be connected
			ll connectingCost = abs(r[i] - b[j]);
			
			// case 1: r[i], b[j] are seperated to the rest
			ll t = sub1Dp[i-1][j-1]; // t is the restCost	
			
			// case 2: r[i] is connected to the rest 
			// in this case, b[j] is seperated to the rest
			t = min(t, sub1Dp[i][j-1]);
			
			// case 3: b[j] is connected to the rest
			// in this case, r[i] is seperated to the rest
			t = min(t, sub1Dp[i-1][j]);
			
			sub1Dp[i][j] = t + connectingCost;
		}
	}
	
	return sub1Dp[n-1][m-1];
}

bool isSub2(vector<int> &r, vector<int> &b) {
	return r.back() < b[0];
}

ll sub2(vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	
	ll rSum = 0;
	for(int i=0; i<n; i++) {
		rSum += r[n-1] - r[i];
	}
	
	ll bSum = 0;
	for(int j=0; j<m; j++) {
		bSum += b[j] - b[0];
	}
	
	ll connectingCost = (ll)(b[0] - r[n-1]) * max(n, m);
	
	return rSum + bSum + connectingCost;
}

bool isSub3(vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	vector<int> v;
	
	int i=0, j=0;
	while(i < n && j < m) {
		if(r[i] < b[j]) {
			v.push_back(1);
			i++;
		}
		else {
			v.push_back(0);
			j++;
		}
	}
	
	for(; i<n; i++)
		v.push_back(1);
	
	for(; j<m; j++)
		v.push_back(0);
	
	int cnt = 1;
	for(int i=1; i<v.size(); i++) {
		if(v[i] == v[i-1]) 
			cnt++;
		else 
			cnt = 1;
		
		if(cnt == 7) return false;
	}
	
	return true;
}

void makeVectors(vector<int> &pos, vector<int> &color, vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	
	int i=0, j=0;
	while(i < n && j < m) {
		if(r[i] < b[j]) {
			pos.push_back(r[i]);
			color.push_back(1);
			i++;
		}
		else {
			pos.push_back(b[j]);
			color.push_back(0);
			j++;
		}
	}
	
	for(; i<n; i++) {
		pos.push_back(r[i]);
		color.push_back(1);
	}
	
	for(; j<m; j++) {
		pos.push_back(b[j]);
		color.push_back(0);
	}
}

vector<int> subVector(vector<int> &v, int st, int ed) {
	vector<int> res;
	for(int i=st; i<=ed; i++) {
		res.push_back(v[i]);
	}
	
	return res;
}


void printVector(vector<int> &v) {
	printf("{");
	for(int i=0; i<v.size(); i++) {
		printf("%d,", v[i]);
	}
	printf("}\n");
}

ll sub3Dp[200010]; // minCost of v[0~i] 

ll sub3(vector<int> &r, vector<int> &b) {
	vector<int> pos, color;
	makeVectors(pos, color, r, b);
	//printVector(v);	// OK
	
	vector<int> leftRed, rightBlue;
	int vSt = -1;
	for(int vIdx=0; vIdx<pos.size(); vIdx++) {
		sub3Dp[vIdx] = MAX;
		rightBlue.push_back(pos[vIdx]);
		
		if(color[vIdx] != color[vIdx+1]) {
			vSt = vIdx + 1;
			break;
		}
	}
	
	int prevL = -1, prevR = -1;
	/*
	printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
	printf("leftRed: "); printVector(leftRed);
	printf("rightBlue: "); printVector(rightBlue);*/
	 // OK
	
	for(int vIdx=vSt; vIdx<pos.size(); vIdx++) {
		sub3Dp[vIdx] = MAX;
		
		if(color[vIdx] != color[vIdx-1]) {
			prevL = prevR + 1;
			prevR = vIdx-1;
			leftRed = rightBlue;
			rightBlue.clear();
			/*
			printf("vIdx = %d\n", vIdx);
			printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
			printf("leftRed: "); printVector(leftRed);
			printf("rightBlue: "); printVector(rightBlue);*/ // OK
		}
		
		rightBlue.push_back(pos[vIdx]);
		//printf("(%d, %d), %d, rightBlue: ", v[vIdx].color, v[vIdx].pos, rightBlue.back()); 
		//printVector(rightBlue);
		
		for(int rSt=prevR; rSt>=prevL; rSt--) {
			vector<int> leftRed = subVector(pos, rSt, prevR);
			//printf("subRed: "); printVector(leftRed);
			ll cost = sub2(leftRed, rightBlue);
			
			if(sub3Dp[rSt] == MAX) {
				if(rSt == prevL) {
					sub3Dp[vIdx] = cost;
					break;
				}
				else continue;
			}
			
			ll rest = sub3Dp[rSt];
			if(sub3Dp[rSt-1] != MAX)
				rest = min(rest, sub3Dp[rSt-1]);
				
			/*if(vIdx == 6) {
				printf("rSt=%d: cost = %lld     rest = %lld\n", rSt, cost, rest);
			}*/
				
			sub3Dp[vIdx] = min(sub3Dp[vIdx], cost + rest);
		}
		
		//printf("sub3Dp[%d] = %lld\n", vIdx, sub3Dp[vIdx]);
	}
	
	return sub3Dp[pos.size()-1];
}

ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size(), m = b.size();
	if(false && isSub1(n, m)) {
		return sub1(r, b);
	}
	else if(false && isSub2(r, b)) {
		return sub2(r, b);
	}
	else if(isSub3(r, b)) {
		return sub3(r, b);
	}
	else return -1;
}

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

wiring.cpp: In function 'bool isSub3(std::vector<int>&, std::vector<int>&)':
wiring.cpp:95:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
wiring.cpp: In function 'void printVector(std::vector<int>&)':
wiring.cpp:147:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for(int i=0; i<v.size(); i++) {
      |               ~^~~~~~~~~
wiring.cpp: In function 'll sub3(std::vector<int>&, std::vector<int>&)':
wiring.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |  for(int vIdx=0; vIdx<pos.size(); vIdx++) {
      |                  ~~~~^~~~~~~~~~~
wiring.cpp:179:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |  for(int vIdx=vSt; vIdx<pos.size(); vIdx++) {
      |                    ~~~~^~~~~~~~~~~

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