-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathTeamBuilder.cpp
More file actions
194 lines (165 loc) · 11 KB
/
TeamBuilder.cpp
File metadata and controls
194 lines (165 loc) · 11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <sstream>
#include <set>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <time.h>
#include <queue>
using namespace std;
#define SIZEOFARRAY(s) sizeof(s)/sizeof(s[0])
/* https://www.topcoder.com/stat?c=problem_statement&pm=2356&rd=4740 */
class TeamBuilder
{
public:
vector<int> specialLocations(vector<string> paths);
};
vector<int> TeamBuilder::specialLocations(vector<string> paths)
{
vector<int> ret(2);
size_t len = paths.size();
vector< vector<int> > tc(len, vector<int> (len) );
for (size_t i = 0; i < len; ++i)
{
for (size_t j = 0; j < len; ++j)
{
tc[i][j] = paths[i][j] - '0' > 0 || i == j;
}
}
for (size_t k = 0; k < len; ++k)
{
for (size_t i = 0; i < len; ++i)
{
if (i != k && tc[i][k])
for (size_t j = 0; j < len; ++j)
{
if (i != j && k != j && tc[k][j])
tc[i][j] = 1;
}
}
}
for (size_t i = 0; i < len; ++i)
{
bool flag = true;
for (size_t j = 0; j < len; ++j)
{
if (!tc[i][j])
{
flag = false;
break;
}
}
if (flag)
++ret[0];
}
for (size_t i = 0; i < len; ++i)
{
bool flag = true;
for (size_t j = 0; j < len; ++j)
{
if (!tc[j][i])
{
flag = false;
break;
}
}
if (flag)
++ret[1];
}
return ret;
}
void TEST(vector<string> paths, vector<int> expected)
{
clock_t start, end;
double cpu_time_used;
start = clock();
TeamBuilder teamBuilder;
vector<int> result = teamBuilder.specialLocations(paths);
assert( result.size() == expected.size() &&
std::equal(result.begin(), result.end(),
expected.begin()) );
end = clock();
cpu_time_used = ((double) (end - start));
cout<<"Time taken : "<<cpu_time_used<<endl;
}
vector< vector<int> > convert(string *list, int n)
{
vector< vector<int> > ret(n, vector<int> (n));
for (int i = 0; i< n; ++i)
{
string str = list[i];
for (int j = 0, len = str.length(); j < len; ++j) {
istringstream iss(str.substr(j,1));
iss >> ret[i][j];
}
}
return ret;
}
template <class T>
vector<T> convertEx(T *list, int n)
{
vector<T> ret;
for (int i = 0; i< n; ++i)
{
ret.push_back(list[i]);
}
return ret;
}
void Test1()
{
string test[] = {"010","000","110"};
int result[] = { 1, 1 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test2()
{
string test[] = {"0110000","1000100","0000001","0010000","0110000","1000010","0001000"};
int result[] = { 1, 3 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test3()
{
string test[] = {"0010","1000","1100","1000"};
int result[] = { 1, 3 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test4()
{
string test[] = {"01000","00100","00010","00001","10000"};
int result[] = { 5, 5 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test5()
{
string test[] = {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000"};
int result[] = { 0, 0 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test6()
{
string test[] = {"01111111111111111111111111111111111111111111111111", "10111111111111111111111111111111111111111111111111", "11011111111111111111111111111111111111111111111111", "11101111111111111111111111111111111111111111111111", "11110111111111111111111111111111111111111111111111", "11111011111111111111111111111111111111111111111111", "11111101111111111111111111111111111111111111111111", "11111110111111111111111111111111111111111111111111", "11111111011111111111111111111111111111111111111111", "11111111101111111111111111111111111111111111111111", "11111111110111111111111111111111111111111111111111", "11111111111011111111111111111111111111111111111111", "11111111111101111111111111111111111111111111111111", "11111111111110111111111111111111111111111111111111", "11111111111111011111111111111111111111111111111111", "11111111111111101111111111111111111111111111111111", "11111111111111110111111111111111111111111111111111", "11111111111111111011111111111111111111111111111111", "11111111111111111101111111111111111111111111111111", "11111111111111111110111111111111111111111111111111", "11111111111111111111011111111111111111111111111111", "11111111111111111111101111111111111111111111111111", "11111111111111111111110111111111111111111111111111", "11111111111111111111111011111111111111111111111111", "11111111111111111111111101111111111111111111111111", "11111111111111111111111110111111111111111111111111", "11111111111111111111111111011111111111111111111111", "11111111111111111111111111101111111111111111111111", "11111111111111111111111111110111111111111111111111", "11111111111111111111111111111011111111111111111111", "11111111111111111111111111111101111111111111111111", "11111111111111111111111111111110111111111111111111", "11111111111111111111111111111111011111111111111111", "11111111111111111111111111111111101111111111111111", "11111111111111111111111111111111110111111111111111", "11111111111111111111111111111111111011111111111111", "11111111111111111111111111111111111101111111111111", "11111111111111111111111111111111111110111111111111", "11111111111111111111111111111111111111011111111111", "11111111111111111111111111111111111111101111111111", "11111111111111111111111111111111111111110111111111", "11111111111111111111111111111111111111111011111111", "11111111111111111111111111111111111111111101111111", "11111111111111111111111111111111111111111110111111", "11111111111111111111111111111111111111111111011111", "11111111111111111111111111111111111111111111101111", "11111111111111111111111111111111111111111111110111", "11111111111111111111111111111111111111111111111011", "11111111111111111111111111111111111111111111111101", "11111111111111111111111111111111111111111111111110"};
int result[] = { 50, 50 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
void Test7()
{
string test[] = {"0000000000000000000000000000000000000000000000", "0000101000000001000000010000000000000000001000", "0000100000000000100000100100000000001000000010", "0000000010000100000000000000000000010000100000", "0000000000001000000000000000000010001000100000", "0000000000000000100010000010000000000000100000", "0000000010000011001000000000000000000000000000", "0001000000000000000000010000000000000000000000", "0000000000000000000000100000000000010000000000", "0000000000000000001000001000000000000000000000", "1000000000000000100000000100001001000000100000", "0000000000000010000000000000110000000000010000", "0010000000000000110001000000000000000010000100", "0000000000000000001000001000000000010000000000", "0100000000000100000000000000110010000000000010", "0000000000000000000000001000000010000000000000", "0100000100000000000010000000000000000000001100", "0000000000010000100010000000010000010100000000", "0000000000001000000010000000000010100100001000", "0000000100100000000000000000100000000001011000", "0000000100000100000000100000000000000000000100", "0000000000000000000000000001000000100000000000", "0000100000000000000000000000000001110000000010", "0000000000000010000000000000000000001000000000", "0000000000001000000100000000000000000000000000", "0000000000000000000000000010001010010000000000", "0000000000000001000000000001000000000000000100", "0000000001000010010000000000000000000000001000", "0000000000000000001100000000000001000000000000", "0000100000000000000000000000000000000000010000", "0000000010001000000000000000000000000000000000", "0000001000000000000001001000000001000000000000", "1100010000000001000101000000000000000000000100", "0000000001000000000000100000000000000000000000", "0000000000100011000100000000010000001000000000", "0010000000000000000000000010000000000100000000", "0000000000000000001000010000000000010000010010", "0000000000000000110100000000000000000000000001", "1000000010000000100000010000000001000000000000", "0001000000100000010000000000010001000000000001", "0000000000000000000000000010000100010001000000", "0000010000000000000010000000000000000000000000", "0000000000100000010000000000000001000100000000", "0000001000000001000000000000000000000000001000", "0000001000000001000001000000000000000000001000", "0000000100000000000000000000100001000000100000"};
int result[] = { 45, 1 };
TEST(convertEx(test, SIZEOFARRAY(test)), convertEx(result, SIZEOFARRAY(result)));
}
int main()
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
cout<<"success";
getchar();
return 0;
}