#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int N;
mt19937 gen(time(NULL));
int rand(int l, int r)
{
uniform_int_distribution<> dis(l, r);
return dis(gen);
}
void answer(int a, int b)
{
if(a>b) swap(a, b);
Bridge(a, b);
}
void solve(vector<int> cand)
{
if(cand.size()==1) return;
int i, j;
int u, v;
u=rand(0, cand.size()-1);
v=rand(0, cand.size()-1);
while(u==v) v=rand(0, cand.size()-1);
u=cand[u]; v=cand[v];
map<int, vector<int>> M;
vector<int> V;
M[u].push_back(u);
M[v].push_back(v);
//for(auto it : cand) printf("%d ", it); printf(" : %d %d\n", u, v);
for(auto now : cand)
{
if(now==u || now==v) continue;
int t=Query(u, v, now);
M[t].push_back(now);
if(t!=u && t!=v) V.push_back(t);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
stable_sort(V.begin(), V.end(), [&](const int &p, const int &q)
{
return Query(u, p, q)==q;
});
V.insert(V.begin(), u);
V.push_back(v);
for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);
for(auto it : M) solve(it.second);
}
void Solve(int _N)
{
int i, j;
N=_N;
vector<int> V;
for(i=0; i<N; i++) V.push_back(i);
solve(V);
}
Compilation message
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);
~^~~~~~~~~
meetings.cpp:28:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:70:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Incorrect |
2 ms |
248 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Incorrect |
2 ms |
248 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Incorrect |
2 ms |
248 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
110 ms |
568 KB |
Wrong Answer [4] |
2 |
Halted |
0 ms |
0 KB |
- |