#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "meetings.h"
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
int Q;
int query(int a, int b, int c)
{
return Query(a,b,c);
}
int N;
vector<ii> edges;
void out()
{
for(int i=0;i<edges.size();i++)
{
Bridge(edges[i].fi,edges[i].se);
}
}
void addedge(int x, int y)
{
edges.pb(mp(x,y));
}
int A,B;
bool cmp(int x, int y)
{
if(x==A) return true;
if(x==B) return false;
if(y==A) return false;
if(y==B) return true;
int z=query(A,x,y);
if(z==x) return true;
else return false;
}
void solve(vi vec)
{
int n=vec.size();
if(n==1) return;
if(n==2)
{
addedge(vec[0],vec[1]);
return ;
}
random_shuffle(vec.begin(),vec.end());
map<int,vi> ma;
for(int i=2;i<n;i++)
{
int x=query(vec[0],vec[1],vec[i]);
ma[x].pb(vec[i]);
}
A=vec[0];B=vec[1];
vi path;
for(auto it = ma.begin(); it != ma.end(); it++)
{
path.pb(it->fi);
}
path.pb(A); path.pb(B);
sort(path.begin(),path.end()); path.erase(unique(path.begin(),path.end()),path.end());
sort(path.begin(),path.end(),cmp);
for(int i=0;i+1<path.size();i++)
{
addedge(path[i],path[i+1]);
}
for(auto it = ma.begin(); it != ma.end(); it++)
{
if(it->fi==A) it->se.pb(A);
if(it->fi==B) it->se.pb(B);
}
for(auto it = ma.begin(); it != ma.end(); it++)
{
solve(it->se);
}
}
void Solve(int N) {
vi vec;
for(int i=0;i<N;i++) vec.pb(i);
solve(vec);
}
Compilation message
meetings.cpp: In function 'void out()':
meetings.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
meetings.cpp: In function 'void solve(vi)':
meetings.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i+1<path.size();i++)
| ~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
336 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
336 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
336 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
326 ms |
648 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |