# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
299887 |
2020-09-15T23:16:34 Z |
YJU |
Meetings (JOI19_meetings) |
C++14 |
|
1183 ms |
1048 KB |
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e3+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
vector<pll> ed;
vector<ll> dg[N];
/*
int Query(ll a,ll b,ll c);
void Bridge(ll a,ll b);
*/
void build(ll nl,ll nr,vector<ll> v){
vector<ll> l,r,midr,midl,line;
l.clear();r.clear();midr.clear();midl.clear();line.clear();
ll id=N-1;
for(ll i:v){
ll x=Query(nl,nr,i);
if(x==nl){
l.pb(i);
}else if(x==nr){
r.pb(i);
}else{
if(x==i)line.pb(i);
dg[x].pb(i);
id=(SZ(dg[x])>SZ(dg[id])?x:id);
}
}
if(SZ(line)==0){ed.pb(mp(nl,nr));}
for(ll i:line){
if(i==id){
for(ll j:dg[i]){
if(j!=i)midl.pb(j);
}
continue;
}
ll x=Query(nl,id,i);
if(x==i){
for(ll j:dg[i])midl.pb(j);
}else{
for(ll j:dg[i])midr.pb(j);
}
}
for(ll i:line)dg[i].clear();
random_shuffle(l.begin(),l.end());
random_shuffle(r.begin(),r.end());
ll ndl=(SZ(l)?l[0]:-1),ndr=(SZ(r)?r[0]:-1);
if(SZ(r))r.erase(r.begin());
if(SZ(l))l.erase(l.begin());
if(ndl!=-1)build(ndl,nl,l);
if(ndr!=-1)build(ndr,nr,r);
if(SZ(line))build(nl,id,midl),build(id,nr,midr);
return ;
}
void Solve(ll n){
srand(clock());
vector<ll> v;
for(int i=2;i<n;i++)v.pb(i);
build(0,1,v);
for(auto i:ed){
if(i.X>i.Y)swap(i.X,i.Y);
Bridge(i.X,i.Y);
}
}
/*
int main(){
ll n;
cin>>n;
Solve(n);
return 0;
}
int Query(ll a,ll b,ll c){
cout<<"Q:"<<a<<" "<<b<<" "<<c<<"\n";
ll y;
cin>>y;
return y;
}
void Bridge(ll a,ll b){
cout<<a<<" "<<b<<"\n";
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
8 ms |
512 KB |
Output is correct |
28 |
Correct |
8 ms |
512 KB |
Output is correct |
29 |
Correct |
9 ms |
512 KB |
Output is correct |
30 |
Correct |
8 ms |
512 KB |
Output is correct |
31 |
Correct |
8 ms |
512 KB |
Output is correct |
32 |
Correct |
8 ms |
512 KB |
Output is correct |
33 |
Correct |
13 ms |
512 KB |
Output is correct |
34 |
Correct |
15 ms |
512 KB |
Output is correct |
35 |
Correct |
13 ms |
512 KB |
Output is correct |
36 |
Correct |
10 ms |
512 KB |
Output is correct |
37 |
Correct |
13 ms |
512 KB |
Output is correct |
38 |
Correct |
12 ms |
512 KB |
Output is correct |
39 |
Correct |
20 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
591 ms |
792 KB |
Output is correct |
2 |
Correct |
661 ms |
760 KB |
Output is correct |
3 |
Correct |
679 ms |
760 KB |
Output is correct |
4 |
Correct |
619 ms |
888 KB |
Output is correct |
5 |
Correct |
687 ms |
888 KB |
Output is correct |
6 |
Correct |
572 ms |
1016 KB |
Output is correct |
7 |
Correct |
663 ms |
892 KB |
Output is correct |
8 |
Correct |
725 ms |
888 KB |
Output is correct |
9 |
Correct |
742 ms |
760 KB |
Output is correct |
10 |
Correct |
675 ms |
892 KB |
Output is correct |
11 |
Correct |
846 ms |
980 KB |
Output is correct |
12 |
Correct |
950 ms |
1016 KB |
Output is correct |
13 |
Correct |
720 ms |
760 KB |
Output is correct |
14 |
Correct |
801 ms |
912 KB |
Output is correct |
15 |
Correct |
762 ms |
1020 KB |
Output is correct |
16 |
Correct |
798 ms |
1016 KB |
Output is correct |
17 |
Correct |
652 ms |
1016 KB |
Output is correct |
18 |
Correct |
727 ms |
1048 KB |
Output is correct |
19 |
Correct |
634 ms |
988 KB |
Output is correct |
20 |
Correct |
870 ms |
760 KB |
Output is correct |
21 |
Correct |
905 ms |
1016 KB |
Output is correct |
22 |
Correct |
719 ms |
788 KB |
Output is correct |
23 |
Correct |
721 ms |
760 KB |
Output is correct |
24 |
Correct |
758 ms |
760 KB |
Output is correct |
25 |
Correct |
831 ms |
760 KB |
Output is correct |
26 |
Correct |
798 ms |
932 KB |
Output is correct |
27 |
Correct |
793 ms |
760 KB |
Output is correct |
28 |
Correct |
793 ms |
888 KB |
Output is correct |
29 |
Correct |
649 ms |
888 KB |
Output is correct |
30 |
Correct |
698 ms |
868 KB |
Output is correct |
31 |
Correct |
729 ms |
888 KB |
Output is correct |
32 |
Correct |
1072 ms |
1016 KB |
Output is correct |
33 |
Correct |
1183 ms |
900 KB |
Output is correct |
34 |
Correct |
9 ms |
512 KB |
Output is correct |
35 |
Correct |
7 ms |
512 KB |
Output is correct |
36 |
Correct |
11 ms |
512 KB |
Output is correct |
37 |
Correct |
7 ms |
512 KB |
Output is correct |
38 |
Correct |
8 ms |
512 KB |
Output is correct |
39 |
Correct |
8 ms |
512 KB |
Output is correct |
40 |
Correct |
12 ms |
512 KB |
Output is correct |
41 |
Correct |
14 ms |
512 KB |
Output is correct |
42 |
Correct |
13 ms |
512 KB |
Output is correct |
43 |
Correct |
8 ms |
512 KB |
Output is correct |
44 |
Correct |
14 ms |
512 KB |
Output is correct |
45 |
Correct |
16 ms |
640 KB |
Output is correct |
46 |
Correct |
21 ms |
512 KB |
Output is correct |
47 |
Correct |
1 ms |
384 KB |
Output is correct |
48 |
Correct |
1 ms |
384 KB |
Output is correct |
49 |
Correct |
1 ms |
384 KB |
Output is correct |
50 |
Correct |
1 ms |
384 KB |
Output is correct |
51 |
Correct |
1 ms |
384 KB |
Output is correct |
52 |
Correct |
1 ms |
384 KB |
Output is correct |
53 |
Correct |
1 ms |
384 KB |
Output is correct |
54 |
Correct |
1 ms |
384 KB |
Output is correct |
55 |
Correct |
1 ms |
384 KB |
Output is correct |
56 |
Correct |
1 ms |
384 KB |
Output is correct |
57 |
Correct |
1 ms |
384 KB |
Output is correct |
58 |
Correct |
1 ms |
384 KB |
Output is correct |
59 |
Correct |
1 ms |
384 KB |
Output is correct |
60 |
Correct |
0 ms |
384 KB |
Output is correct |
61 |
Correct |
1 ms |
384 KB |
Output is correct |
62 |
Correct |
1 ms |
384 KB |
Output is correct |
63 |
Correct |
0 ms |
384 KB |
Output is correct |
64 |
Correct |
0 ms |
384 KB |
Output is correct |
65 |
Correct |
0 ms |
384 KB |
Output is correct |
66 |
Correct |
0 ms |
384 KB |
Output is correct |
67 |
Correct |
0 ms |
384 KB |
Output is correct |
68 |
Correct |
1 ms |
384 KB |
Output is correct |
69 |
Correct |
1 ms |
384 KB |
Output is correct |
70 |
Correct |
0 ms |
384 KB |
Output is correct |
71 |
Correct |
1 ms |
384 KB |
Output is correct |
72 |
Correct |
0 ms |
384 KB |
Output is correct |