Submission #896848

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896848	2024-01-02T09:41:58 Z	joonwu04	Wiring (IOI17_wiring)	C++17	Compilation error	0 ms	0 KB

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> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
	
	ll lSum = 0;
	for(int i=lSt; i<=lEd; i++) {
		lSum += left[lEd] - left[i];
	}
	
	ll rSum = 0;
	for(int j=rSt; j<=rEd; j++) {
		rSum += right[j] - right[rSt];
	}
	
	ll connectingCost = (ll)(right[rSt] - left[lEd]) * max(lEd-lSt+1, rEd-rSt+1);
	
	return lSum + rSum + 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(i == n) { v.push_back(0); j++;}
		else if(j == m) { v.push_back(1); i++;}
		else if(r[i] < b[j]) { v.push_back(1); i++;}
		else { v.push_back(0); j++;}
	}
	
	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> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
	int n = r.size(), m = b.size();
	
	int i=0, j=0;
	while(i < n || j < m) {
		if(i == n) {color.push_back(0); idx.push_back(j); j++;}
		else if(j == m) {color.push_back(1); idx.push_back(i); i++;}
		else if(r[i] < b[j]) {color.push_back(1); idx.push_back(i); i++;}
		else {color.push_back(0); idx.push_back(j); j++;}
	}
}
 
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> color, rbIdx;
	makeVectors(color, rbIdx, r, b);
	int vSize = color.size();
	//printVector(color);	// OK
	
	int vRightSt=-1, vRightEd=-1;
	int vSt = -1;
	for(int vIdx=0; vIdx<vSize; vIdx++) {
		sub3Dp[vIdx] = MAX;
		
		if(color[vIdx] != color[vIdx+1]) {
			vSt = vIdx + 1;
			vRightSt = 0;
			vRightEd = vIdx;
			break;
		}
	}
	
	int vPrevL = -1, vPrevR = -1;
	/*
	printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
	printf("leftRed: "); printVector(leftRed);
	printf("rightBlue: "); printVector(rightBlue);*/
	 // OK
	int vLeftEd=-1;
	for(int vIdx=vSt; vIdx<vSize; vIdx++) {
		sub3Dp[vIdx] = MAX;
		
		if(color[vIdx] != color[vIdx-1]) {
			vPrevL = vRightSt;
			vPrevR = vRightEd;
			vRightSt = vIdx;
			vLeftEd = vPrevR;
			
			//printf("vIdx = %d\n", vIdx);
			//printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
		}
		
		vRightEd = vIdx;
		
		for(int vLeftSt=vPrevR; vLeftSt>=vPrevL; vLeftSt--) {
			bool reversed = color[vIdx] == 1;
			
			//printf("(vIdx, leftSt, leftEd, rightSt, rightEd) = (%d, %d, %d, %d, %d)\n", vIdx, leftSt, leftEd, rightSt, rightEd);
			ll cost;
			if(reversed) {
				cost = sub2(b, r, rbIdx[vLeftSt], rbIdx[vLeftEd], rbIdx[vRightSt], rbIdx[vRightEd]);
				//printf("cost=%lld\n", cost);
			}
			else cost = sub2(r, b, rbIdx[vLeftSt], rbIdx[vLeftEd], rbIdx[vRightSt], rbIdx[vRightEd]);
			
			if(sub3Dp[vLeftSt] == MAX) {
				if(vLeftSt == vPrevL) {
					sub3Dp[vIdx] = cost;
					break;
				}
				else continue;
			}
			
			ll rest = sub3Dp[vLeftSt];
			if(sub3Dp[vLeftSt-1] != MAX)
				rest = min(rest, sub3Dp[vLeftSt-1]);
			
			//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[vSize-1];
}
 
ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size(), m = b.size();
	if(isSub1(n, m)) {
		return sub1(r, b);
	}
	else if(isSub2(r, b)) {
		return sub2(r, b, 0, n-1, 0, m-1);
	}
	else if(isSub3(r, b)) {
		return sub3(r, b);
	}
	
	return -1;
}

Compilation message

wiring.cpp:19:9: error: 'vector' was not declared in this scope
   19 | ll sub1(vector<int> &r, vector<int> &b) {
      |         ^~~~~~
wiring.cpp:3:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    2 | #include <iostream>
  +++ |+#include <vector>
    3 | #define MAX 1000000000000000000
wiring.cpp:19:16: error: expected primary-expression before 'int'
   19 | ll sub1(vector<int> &r, vector<int> &b) {
      |                ^~~
wiring.cpp:19:25: error: 'vector' was not declared in this scope
   19 | ll sub1(vector<int> &r, vector<int> &b) {
      |                         ^~~~~~
wiring.cpp:19:25: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:19:32: error: expected primary-expression before 'int'
   19 | ll sub1(vector<int> &r, vector<int> &b) {
      |                                ^~~
wiring.cpp:19:39: error: expression list treated as compound expression in initializer [-fpermissive]
   19 | ll sub1(vector<int> &r, vector<int> &b) {
      |                                       ^
wiring.cpp:50:13: error: 'vector' was not declared in this scope
   50 | bool isSub2(vector<int> &r, vector<int> &b) {
      |             ^~~~~~
wiring.cpp:50:13: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:50:20: error: expected primary-expression before 'int'
   50 | bool isSub2(vector<int> &r, vector<int> &b) {
      |                    ^~~
wiring.cpp:50:29: error: 'vector' was not declared in this scope
   50 | bool isSub2(vector<int> &r, vector<int> &b) {
      |                             ^~~~~~
wiring.cpp:50:29: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:50:36: error: expected primary-expression before 'int'
   50 | bool isSub2(vector<int> &r, vector<int> &b) {
      |                                    ^~~
wiring.cpp:50:43: error: expression list treated as compound expression in initializer [-fpermissive]
   50 | bool isSub2(vector<int> &r, vector<int> &b) {
      |                                           ^
wiring.cpp:54:9: error: 'vector' was not declared in this scope
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |         ^~~~~~
wiring.cpp:54:9: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:54:16: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                ^~~
wiring.cpp:54:28: error: 'vector' was not declared in this scope
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                            ^~~~~~
wiring.cpp:54:28: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:54:35: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                   ^~~
wiring.cpp:54:48: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                                ^~~
wiring.cpp:54:57: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                                         ^~~
wiring.cpp:54:66: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                                                  ^~~
wiring.cpp:54:75: error: expected primary-expression before 'int'
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                                                           ^~~
wiring.cpp:54:82: error: expression list treated as compound expression in initializer [-fpermissive]
   54 | ll sub2(vector<int> &left, vector<int> &right, int lSt, int lEd, int rSt, int rEd) {
      |                                                                                  ^
wiring.cpp:71:13: error: 'vector' was not declared in this scope
   71 | bool isSub3(vector<int> &r, vector<int> &b) {
      |             ^~~~~~
wiring.cpp:71:13: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:71:20: error: expected primary-expression before 'int'
   71 | bool isSub3(vector<int> &r, vector<int> &b) {
      |                    ^~~
wiring.cpp:71:29: error: 'vector' was not declared in this scope
   71 | bool isSub3(vector<int> &r, vector<int> &b) {
      |                             ^~~~~~
wiring.cpp:71:29: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:71:36: error: expected primary-expression before 'int'
   71 | bool isSub3(vector<int> &r, vector<int> &b) {
      |                                    ^~~
wiring.cpp:71:43: error: expression list treated as compound expression in initializer [-fpermissive]
   71 | bool isSub3(vector<int> &r, vector<int> &b) {
      |                                           ^
wiring.cpp:94:6: error: variable or field 'makeVectors' declared void
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |      ^~~~~~~~~~~
wiring.cpp:94:18: error: 'vector' was not declared in this scope
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                  ^~~~~~
wiring.cpp:94:18: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:94:25: error: expected primary-expression before 'int'
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                         ^~~
wiring.cpp:94:38: error: 'vector' was not declared in this scope
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                      ^~~~~~
wiring.cpp:94:38: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:94:45: error: expected primary-expression before 'int'
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                             ^~~
wiring.cpp:94:56: error: 'vector' was not declared in this scope
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                                        ^~~~~~
wiring.cpp:94:56: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:94:63: error: expected primary-expression before 'int'
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                                               ^~~
wiring.cpp:94:72: error: 'vector' was not declared in this scope
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                                                        ^~~~~~
wiring.cpp:94:72: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:94:79: error: expected primary-expression before 'int'
   94 | void makeVectors(vector<int> &color, vector<int> &idx, vector<int> &r, vector<int> &b) {
      |                                                                               ^~~
wiring.cpp:106:6: error: variable or field 'printVector' declared void
  106 | void printVector(vector<int> &v) {
      |      ^~~~~~~~~~~
wiring.cpp:106:18: error: 'vector' was not declared in this scope
  106 | void printVector(vector<int> &v) {
      |                  ^~~~~~
wiring.cpp:106:18: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:106:25: error: expected primary-expression before 'int'
  106 | void printVector(vector<int> &v) {
      |                         ^~~
wiring.cpp:116:9: error: 'vector' was not declared in this scope
  116 | ll sub3(vector<int> &r, vector<int> &b) {
      |         ^~~~~~
wiring.cpp:116:9: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:116:16: error: expected primary-expression before 'int'
  116 | ll sub3(vector<int> &r, vector<int> &b) {
      |                ^~~
wiring.cpp:116:25: error: 'vector' was not declared in this scope
  116 | ll sub3(vector<int> &r, vector<int> &b) {
      |                         ^~~~~~
wiring.cpp:116:25: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:116:32: error: expected primary-expression before 'int'
  116 | ll sub3(vector<int> &r, vector<int> &b) {
      |                                ^~~
wiring.cpp:116:39: error: expression list treated as compound expression in initializer [-fpermissive]
  116 | ll sub3(vector<int> &r, vector<int> &b) {
      |                                       ^
wiring.cpp:192:21: error: 'vector' was not declared in this scope
  192 | ll min_total_length(vector<int> r, vector<int> b) {
      |                     ^~~~~~
wiring.cpp:192:21: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:192:28: error: expected primary-expression before 'int'
  192 | ll min_total_length(vector<int> r, vector<int> b) {
      |                            ^~~
wiring.cpp:192:36: error: 'vector' was not declared in this scope
  192 | ll min_total_length(vector<int> r, vector<int> b) {
      |                                    ^~~~~~
wiring.cpp:192:36: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:192:43: error: expected primary-expression before 'int'
  192 | ll min_total_length(vector<int> r, vector<int> b) {
      |                                           ^~~
wiring.cpp:192:49: error: expression list treated as compound expression in initializer [-fpermissive]
  192 | ll min_total_length(vector<int> r, vector<int> b) {
      |                                                 ^