# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
896850 |
2024-01-02T09:42:26 Z |
joonwu04 |
Wiring (IOI17_wiring) |
C++17 |
|
33 ms |
8428 KB |
#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: In function 'bool isSub3(std::vector<int>&, std::vector<int>&)':
wiring.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=1; i<v.size(); i++) {
| ~^~~~~~~~~
wiring.cpp: In function 'void printVector(std::vector<int>&)':
wiring.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0; i<v.size(); i++) {
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
14 ms |
3072 KB |
Output is correct |
4 |
Correct |
14 ms |
2908 KB |
Output is correct |
5 |
Correct |
14 ms |
2908 KB |
Output is correct |
6 |
Correct |
19 ms |
3932 KB |
Output is correct |
7 |
Correct |
19 ms |
3900 KB |
Output is correct |
8 |
Correct |
18 ms |
3784 KB |
Output is correct |
9 |
Correct |
19 ms |
3772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
28 ms |
8328 KB |
Output is correct |
4 |
Correct |
30 ms |
7864 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
448 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
29 ms |
8232 KB |
Output is correct |
19 |
Correct |
28 ms |
8376 KB |
Output is correct |
20 |
Correct |
33 ms |
8356 KB |
Output is correct |
21 |
Correct |
28 ms |
8380 KB |
Output is correct |
22 |
Correct |
32 ms |
8372 KB |
Output is correct |
23 |
Correct |
31 ms |
8428 KB |
Output is correct |
24 |
Correct |
31 ms |
8352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
16 ms |
4300 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '-1' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
14 ms |
3072 KB |
Output is correct |
20 |
Correct |
14 ms |
2908 KB |
Output is correct |
21 |
Correct |
14 ms |
2908 KB |
Output is correct |
22 |
Correct |
19 ms |
3932 KB |
Output is correct |
23 |
Correct |
19 ms |
3900 KB |
Output is correct |
24 |
Correct |
18 ms |
3784 KB |
Output is correct |
25 |
Correct |
19 ms |
3772 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
344 KB |
Output is correct |
28 |
Correct |
28 ms |
8328 KB |
Output is correct |
29 |
Correct |
30 ms |
7864 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
448 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
0 ms |
604 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
29 ms |
8232 KB |
Output is correct |
44 |
Correct |
28 ms |
8376 KB |
Output is correct |
45 |
Correct |
33 ms |
8356 KB |
Output is correct |
46 |
Correct |
28 ms |
8380 KB |
Output is correct |
47 |
Correct |
32 ms |
8372 KB |
Output is correct |
48 |
Correct |
31 ms |
8428 KB |
Output is correct |
49 |
Correct |
31 ms |
8352 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Incorrect |
16 ms |
4300 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '-1' |
52 |
Halted |
0 ms |
0 KB |
- |