### 10037: Bridge

Posted:

**Sun Oct 12, 2003 2:16 am**I'm getting WA for my submission below. Could someone please give me an input for which my submission fails, and what the expected output is?

[cpp]

#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

int max(int n1, int n2) {

return n1 >= n2 ? n1 : n2;

}

int min(int n1, int n2) {

return n1 <= n2 ? n1 : n2;

}

int solveBridgeProblem(vector<int> times, bool print) {

bool onLeftBank[1000];

bool onRightBank[1000];

int cnt = times.size();

for (int i = 0; i < 1000; i++) {

onLeftBank

[cpp]

#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

int max(int n1, int n2) {

return n1 >= n2 ? n1 : n2;

}

int min(int n1, int n2) {

return n1 <= n2 ? n1 : n2;

}

int solveBridgeProblem(vector<int> times, bool print) {

bool onLeftBank[1000];

bool onRightBank[1000];

int cnt = times.size();

for (int i = 0; i < 1000; i++) {

onLeftBank

*= (i < cnt);*

onRightBankonRightBank

*= false;*

}

int totalTime = 0;

for (int i = 0; i < cnt - 1; i++) {

int t1;

int t2;

bool t1Found = false;

bool t2Found = false;

int index;

if (i % 2 == 0) {

index = 0;

}

else {

index = cnt - 1;

}

while (!t1Found || !t2Found) {

if (onLeftBank[index]) {

if (!t1Found) {

t1 = index;

t1Found = true;

}

else {

t2 = index;

t2Found = true;

}

}

if (i % 2 == 0) {

index++;

}

else {

index--;

}

}

totalTime += max(times[t1], times[t2]);

if (print) {

cout << min(times[t1], times[t2]) << " "

<< max(times[t1], times[t2]) << endl;

}

onLeftBank[t1] = false;

onLeftBank[t2] = false;

onRightBank[t1] = true;

onRightBank[t2] = true;

if (i < cnt - 2) {

index = 0;

t1Found = false;

while (!t1Found) {

if (onRightBank[index]) {

t1 = index;

t1Found = true;

}

index++;

}

totalTime += times[t1];

if (print) {

cout << times[t1] << endl;

}

onLeftBank[t1] = true;

onRightBank[t1] = false;

}

}

return totalTime;

}

int getTotalTime(vector<int> times) {

return solveBridgeProblem(times, false);

}

void printCrossings(vector<int> times) {

solveBridgeProblem(times, true);

}

int main (int argc, const char * argv[]) {

int testCaseCnt;

cin >> testCaseCnt;

for (int i = 0; i < testCaseCnt; i++) {

string s;

getline(cin, s);

int itemCnt;

cin >> itemCnt;

vector<int> times;

for (int j = 0; j < itemCnt; j++) {

int time;

cin >> time;

times.push_back(time);

}

sort(×[0], ×[itemCnt]);

int totalTime = getTotalTime(times);

cout << totalTime << endl;

printCrossings(times);

cout << endl;

}

return 0;

}

[/cpp]}

int totalTime = 0;

for (int i = 0; i < cnt - 1; i++) {

int t1;

int t2;

bool t1Found = false;

bool t2Found = false;

int index;

if (i % 2 == 0) {

index = 0;

}

else {

index = cnt - 1;

}

while (!t1Found || !t2Found) {

if (onLeftBank[index]) {

if (!t1Found) {

t1 = index;

t1Found = true;

}

else {

t2 = index;

t2Found = true;

}

}

if (i % 2 == 0) {

index++;

}

else {

index--;

}

}

totalTime += max(times[t1], times[t2]);

if (print) {

cout << min(times[t1], times[t2]) << " "

<< max(times[t1], times[t2]) << endl;

}

onLeftBank[t1] = false;

onLeftBank[t2] = false;

onRightBank[t1] = true;

onRightBank[t2] = true;

if (i < cnt - 2) {

index = 0;

t1Found = false;

while (!t1Found) {

if (onRightBank[index]) {

t1 = index;

t1Found = true;

}

index++;

}

totalTime += times[t1];

if (print) {

cout << times[t1] << endl;

}

onLeftBank[t1] = true;

onRightBank[t1] = false;

}

}

return totalTime;

}

int getTotalTime(vector<int> times) {

return solveBridgeProblem(times, false);

}

void printCrossings(vector<int> times) {

solveBridgeProblem(times, true);

}

int main (int argc, const char * argv[]) {

int testCaseCnt;

cin >> testCaseCnt;

for (int i = 0; i < testCaseCnt; i++) {

string s;

getline(cin, s);

int itemCnt;

cin >> itemCnt;

vector<int> times;

for (int j = 0; j < itemCnt; j++) {

int time;

cin >> time;

times.push_back(time);

}

sort(×[0], ×[itemCnt]);

int totalTime = getTotalTime(times);

cout << totalTime << endl;

printCrossings(times);

cout << endl;

}

return 0;

}

[/cpp]