#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e3 + 5, MAXN = 1e7 + 5;
const long long oo = 1e9 + 7, mod = 1e9 + 7;
int n;
vector<int> vis[N];
int sz[N];
//vector<ii> bridge;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
temp = (temp + (r - l + 1)) % (r - l + 1);
return temp + l;
}
int query(int a, int b, int c){
//cout << a << " " << b << " " << c << "\n";
return Query(a - 1, b - 1, c - 1) + 1;
}
void bridge(int a, int b){
//cout << min(a, b) << " " << max(a, b) << "\n";
Bridge(min(a, b) - 1, max(a, b) - 1);
}
bool ck[N];
void solve(vector<int> x){
for(int i = 1; i <= n; i++) ck[i] = 0;
if(x.size() <= 1) return;
if(x.size() == 2){
bridge(x[0], x[1]);
return;
}
int temp0 = rnd(0, x.size() - 1), temp1 = rnd(0, x.size() - 1), temp2 = rnd(0, x.size() - 1);
while(temp1 == temp0) temp1 = rnd(0, x.size() - 1);
while(temp2 == temp0 || temp2 == temp1) temp2 = rnd(0, x.size() - 1);
int node = query(x[temp0], x[temp1], x[temp2]);
int node2 = (x[0] == node ? x[1] : x[0]);
//cout << temp << " " << node << " " << node2 << "\n";
//assert(node != node2);
for(auto it : x){
if(it == node || it == node2) continue;
int temp = query(node, node2, it);
if(temp == node){
ck[it] = 1;
continue;
}
node2 = temp;
}
//cout << node << " " << node2 << "\n";
bridge(node, node2);
vector<int> x1, x2;
x1.pb(node), x2.pb(node2);
for(auto it : x){
if(it == node || it == node2) continue;
//int temp = query(node, node2, it);
//assert(temp == node || temp == node2);
if(ck[it]) x1.pb(it);
else x2.pb(it);
}
solve(x1), solve(x2);
}
void Solve(int _n){
n = _n;
vector<int> str;
for(int i = 1; i <= n; i++) str.pb(i);
solve(str);
}
/*
5
0 1
0 2
1 3
1 4
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
1 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
1 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
27 |
Correct |
6 ms |
336 KB |
Output is correct |
28 |
Correct |
5 ms |
336 KB |
Output is correct |
29 |
Correct |
5 ms |
336 KB |
Output is correct |
30 |
Correct |
6 ms |
432 KB |
Output is correct |
31 |
Correct |
6 ms |
448 KB |
Output is correct |
32 |
Correct |
9 ms |
336 KB |
Output is correct |
33 |
Correct |
17 ms |
464 KB |
Output is correct |
34 |
Correct |
15 ms |
464 KB |
Output is correct |
35 |
Correct |
13 ms |
444 KB |
Output is correct |
36 |
Correct |
5 ms |
336 KB |
Output is correct |
37 |
Correct |
8 ms |
464 KB |
Output is correct |
38 |
Correct |
7 ms |
464 KB |
Output is correct |
39 |
Correct |
7 ms |
464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
554 ms |
744 KB |
Output is correct |
2 |
Correct |
637 ms |
776 KB |
Output is correct |
3 |
Correct |
564 ms |
708 KB |
Output is correct |
4 |
Correct |
662 ms |
696 KB |
Output is correct |
5 |
Correct |
616 ms |
632 KB |
Output is correct |
6 |
Correct |
424 ms |
704 KB |
Output is correct |
7 |
Correct |
657 ms |
956 KB |
Output is correct |
8 |
Correct |
720 ms |
736 KB |
Output is correct |
9 |
Correct |
663 ms |
720 KB |
Output is correct |
10 |
Correct |
587 ms |
944 KB |
Output is correct |
11 |
Correct |
717 ms |
724 KB |
Output is correct |
12 |
Correct |
545 ms |
848 KB |
Output is correct |
13 |
Correct |
499 ms |
712 KB |
Output is correct |
14 |
Correct |
632 ms |
788 KB |
Output is correct |
15 |
Correct |
629 ms |
684 KB |
Output is correct |
16 |
Correct |
637 ms |
744 KB |
Output is correct |
17 |
Correct |
641 ms |
804 KB |
Output is correct |
18 |
Correct |
577 ms |
804 KB |
Output is correct |
19 |
Correct |
605 ms |
976 KB |
Output is correct |
20 |
Correct |
699 ms |
724 KB |
Output is correct |
21 |
Correct |
761 ms |
808 KB |
Output is correct |
22 |
Correct |
660 ms |
948 KB |
Output is correct |
23 |
Correct |
662 ms |
848 KB |
Output is correct |
24 |
Correct |
729 ms |
724 KB |
Output is correct |
25 |
Correct |
733 ms |
868 KB |
Output is correct |
26 |
Correct |
718 ms |
792 KB |
Output is correct |
27 |
Correct |
744 ms |
780 KB |
Output is correct |
28 |
Correct |
773 ms |
724 KB |
Output is correct |
29 |
Correct |
618 ms |
712 KB |
Output is correct |
30 |
Correct |
699 ms |
992 KB |
Output is correct |
31 |
Correct |
691 ms |
828 KB |
Output is correct |
32 |
Correct |
624 ms |
816 KB |
Output is correct |
33 |
Correct |
619 ms |
972 KB |
Output is correct |
34 |
Correct |
7 ms |
336 KB |
Output is correct |
35 |
Correct |
6 ms |
464 KB |
Output is correct |
36 |
Correct |
6 ms |
464 KB |
Output is correct |
37 |
Correct |
8 ms |
396 KB |
Output is correct |
38 |
Correct |
8 ms |
452 KB |
Output is correct |
39 |
Correct |
7 ms |
336 KB |
Output is correct |
40 |
Correct |
13 ms |
464 KB |
Output is correct |
41 |
Correct |
13 ms |
476 KB |
Output is correct |
42 |
Correct |
12 ms |
396 KB |
Output is correct |
43 |
Correct |
5 ms |
336 KB |
Output is correct |
44 |
Correct |
8 ms |
468 KB |
Output is correct |
45 |
Correct |
10 ms |
480 KB |
Output is correct |
46 |
Correct |
7 ms |
452 KB |
Output is correct |
47 |
Correct |
1 ms |
336 KB |
Output is correct |
48 |
Correct |
1 ms |
376 KB |
Output is correct |
49 |
Correct |
1 ms |
336 KB |
Output is correct |
50 |
Correct |
1 ms |
336 KB |
Output is correct |
51 |
Correct |
1 ms |
336 KB |
Output is correct |
52 |
Correct |
1 ms |
336 KB |
Output is correct |
53 |
Correct |
1 ms |
336 KB |
Output is correct |
54 |
Correct |
1 ms |
336 KB |
Output is correct |
55 |
Correct |
1 ms |
336 KB |
Output is correct |
56 |
Correct |
1 ms |
404 KB |
Output is correct |
57 |
Correct |
1 ms |
336 KB |
Output is correct |
58 |
Correct |
1 ms |
384 KB |
Output is correct |
59 |
Correct |
1 ms |
336 KB |
Output is correct |
60 |
Correct |
0 ms |
336 KB |
Output is correct |
61 |
Correct |
1 ms |
336 KB |
Output is correct |
62 |
Correct |
0 ms |
336 KB |
Output is correct |
63 |
Correct |
0 ms |
284 KB |
Output is correct |
64 |
Correct |
1 ms |
336 KB |
Output is correct |
65 |
Correct |
0 ms |
336 KB |
Output is correct |
66 |
Correct |
0 ms |
336 KB |
Output is correct |
67 |
Correct |
0 ms |
336 KB |
Output is correct |
68 |
Correct |
0 ms |
336 KB |
Output is correct |
69 |
Correct |
0 ms |
336 KB |
Output is correct |
70 |
Correct |
0 ms |
336 KB |
Output is correct |
71 |
Correct |
0 ms |
336 KB |
Output is correct |
72 |
Correct |
0 ms |
336 KB |
Output is correct |