#include "meetings.h"
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
#define MAXN 2005
int res[MAXN][MAXN];
int cmpc;
vector<int> X[MAXN];
bitset<MAXN> chk;
bool cmp(int a, int b) {
if(a == b) return false;
if(res[a][b] != 0) return res[a][b] == 1;
if(res[b][a] != 0) return res[b][a] == 1;
if(Query(cmpc, a, b) == a) {
res[a][b] = 1;
res[b][a] = -1;
return true;
}
else {
res[a][b] = -1;
res[b][a] = 1;
return false;
}
}
void brid(int a, int b) {
Bridge(min(a, b), max(a, b));
}
void f(vector<int> v) {
/*
printf("f(v = [");
for(auto a : v) printf("%d ", a);
printf("])\n");
*/
if(v.size() <= 1) return;
if(v.size() == 2) {
brid(v[0], v[1]);
return;
}
random_shuffle(v.begin(), v.end());
vector<int> L;
int alpha = v[0], beta = v[1];
for(auto a : v) {
X[a].clear();
chk[a] = false;
}
for(int i = 2; i < v.size(); i++) {
int t = Query(alpha, beta, v[i]);
//printf("alpha = %d, beta = %d, v[i] = %d, t = %d\n", alpha, beta, v[i], t);
if(t == alpha) {
L.push_back(alpha);
X[alpha].push_back(alpha);
alpha = v[i];
}
else if(t == beta) {
L.push_back(beta);
X[beta].push_back(beta);
beta = v[i];
}
else {
if(!chk[t]) L.push_back(t);
chk[t] = true;
X[t].push_back(v[i]);
}
}
cmpc = alpha;
for(auto a : L) for(auto b : L) res[a][b] = 0;
sort(L.begin(), L.end(), cmp);
/*
printf("alpha = %d, beta = %d, L = [", alpha, beta);
for(auto a : L) printf("%d ", a);
printf("]\n");
*/
if(L.empty()) brid(alpha, beta);
else {
brid(alpha, L[0]);
for(int i = 0; i < L.size() - 1; i++) brid(L[i], L[i + 1]);
brid(L.back(), beta);
}
for(auto a : L) f(X[a]);
}
void Solve(int N) {
vector<int> v(N);
for(int i = 0; i < N; i++) v[i] = i;
f(v);
}
Compilation message
meetings.cpp: In function 'void f(std::vector<int>)':
meetings.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 2; i < v.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size() - 1; i++) brid(L[i], L[i + 1]);
~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [3] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [3] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [3] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
143 ms |
852 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |