#include "meetings.h"
#include <vector>
#include <ctime>
using namespace std;
vector<pair<int, int>> T;
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 = Query(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 = Query(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 = Query(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 = Query(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:9: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:9:44: error: 'rand' was not declared in this scope
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:31:15: error: 'rand' was not declared in this scope
int v = vec[rand() % vec.size()], cnt = 0;
^~~~
meetings.cpp:39:16: error: 'cnt' was not declared in this scope
if (S == v) cnt++;
^~~
meetings.cpp:39:16: note: suggested alternative: 'int'
if (S == v) cnt++;
^~~
int
meetings.cpp:42:7: error: 'cnt' was not declared in this scope
if (cnt <= 2) continue;
^~~
meetings.cpp:42:7: note: suggested alternative: 'int'
if (cnt <= 2) continue;
^~~
int
meetings.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int t = 0; t < vec.size(); t++) {
~~^~~~~~~~~~~~
meetings.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:62: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:74:2: error: 'srand' was not declared in this scope
srand((unsigned)time(NULL));
^~~~~
meetings.cpp:74:2: note: suggested alternative: 'signed'
srand((unsigned)time(NULL));
^~~~~
signed
meetings.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
