#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <ctime>
#include <map>
using namespace std;
vector<pair<int, int>> T;
map<tuple<int, int, int>, int> Map;
int Ask(int a1, int a2, int a3) {
int v[3] = { a1, a2, a3 }; sort(v, v + 3);
a1 = v[0]; a2 = v[1]; a3 = v[2];
if (Map[make_tuple(a1, a2, a3)] >= 1) return Map[make_tuple(a1, a2, a3)];
int x = Query(a1, a2, a3);
Map[make_tuple(a1, a2, a3)] = x;
return x;
}
vector<int> random_shuffle(vector<int> I) {
for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
return I;
}
void dfs(vector<int> vec) {
// サイズが 1, 2, 3 のときに場合分け
if (vec.size() == 1) return;
if (vec.size() == 2) {
T.push_back(make_pair(vec[0], vec[1]));
return;
}
if (vec.size() == 3) {
int S = Ask(vec[0], vec[1], vec[2]);
if (vec[0] != S) T.push_back(make_pair(vec[0], S));
if (vec[1] != S) T.push_back(make_pair(vec[1], S));
if (vec[2] != S) T.push_back(make_pair(vec[2], S));
return;
}
vec = random_shuffle(vec);
while (true) {
// 乱択アルゴリズムで重心を見つける
int v = vec[rand() % vec.size()], cnt = 0;
for (int t = 0; t < 8; t++) {
int v1 = v, v2 = v;
while (v1 == v2 || v1 == v || v2 == v) {
v1 = vec[rand() % vec.size()];
v2 = vec[rand() % vec.size()];
}
int S = Ask(v, v1, v2);
if (S == v) cnt++;
}
if (cnt <= 2) continue;
// 連結成分ごとに分ける
vector<int>col(vec.size(), -1); int cnts = 0;
for (int t = 0; t < vec.size(); t++) {
if (col[t] >= 0 || vec[t] == v) continue;
cnts++; col[t] = cnts;
for (int j = 0; j < vec.size(); j++) {
if (col[j] >= 0 || vec[j] == v) continue;
int S = Ask(v, vec[t], vec[j]);
if (S != v) { col[j] = cnts; }
}
}
for (int t = 1; t <= cnts; t++) {
vector<int>E;
for (int j = 0; j < vec.size(); j++) {
if (col[j] == t) E.push_back(vec[j]);
}
int cur = E[0];
for (int j = 1; j < E.size(); j++) {
int F = Ask(v, cur, E[j]);
if (F == E[j]) cur = E[j];
}
T.push_back(make_pair(v, cur));
dfs(E);
}
break;
}
}
void Solve(int N) {
srand((unsigned)time(NULL));
vector<int> vec;
for (int i = 0; i < N; i++) vec.push_back(i);
dfs(vec);
for (int i = 0; i < T.size(); i++) {
if (T[i].first > T[i].second) swap(T[i].first, T[i].second);
Bridge(T[i].first, T[i].second);
}
return;
}
Compilation message
meetings.cpp: In function 'std::vector<int> random_shuffle(std::vector<int>)':
meetings.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
~~^~~~~~~~~~
meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int t = 0; t < vec.size(); t++) {
~~^~~~~~~~~~~~
meetings.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < E.size(); j++) {
~~^~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
296 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
252 KB |
Output is correct |
7 |
Correct |
2 ms |
296 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
296 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
252 KB |
Output is correct |
7 |
Correct |
2 ms |
296 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
424 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
296 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
252 KB |
Output is correct |
7 |
Correct |
2 ms |
296 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
424 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
22 ms |
764 KB |
Output is correct |
28 |
Correct |
20 ms |
680 KB |
Output is correct |
29 |
Correct |
22 ms |
760 KB |
Output is correct |
30 |
Correct |
21 ms |
760 KB |
Output is correct |
31 |
Correct |
22 ms |
760 KB |
Output is correct |
32 |
Correct |
20 ms |
760 KB |
Output is correct |
33 |
Correct |
25 ms |
760 KB |
Output is correct |
34 |
Correct |
31 ms |
892 KB |
Output is correct |
35 |
Correct |
30 ms |
864 KB |
Output is correct |
36 |
Correct |
25 ms |
760 KB |
Output is correct |
37 |
Correct |
21 ms |
704 KB |
Output is correct |
38 |
Correct |
22 ms |
700 KB |
Output is correct |
39 |
Correct |
19 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2608 ms |
3972 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |