#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e5 + 10;
int h[N], mark[N];
bool cmp(int obj1, int obj2) { return h[obj1] < h[obj2];}
vi createFunTour(int n, int Q) {
//int H = hoursRequired(0, N - 1);
//int A = attractionsBehind(0, N - 1);
int root = 0, mn = 1e9;
for (int i = 1; i < n; ++i)
{
int tmp = attractionsBehind(0, i);
if (tmp >= (n + 1) / 2 && tmp < mn) mn = tmp, root = i;
}
vi sub_root;
h[root] = 0;
mark[root] = 1;
for (int i = 0; i < n; ++i)
if (i!=root)
{
h[i] = hoursRequired(root, i);
if (h[i] == 1) sub_root.eb(i), mark[i] = 1;
else mark[i] = 0;
}
vi subT[3];
int n_sub = sub_root.size();
for (int i = 0; i < n_sub; ++i) subT[i].eb(sub_root[i]);
for (int i = 0; i < n; ++i)
if (!mark[i])
{
int belong = n_sub - 1;
for (int j = 0; j < n_sub - 1; ++j)
if (hoursRequired(sub_root[j], i) + 1 == h[i])
{
belong = j;
break;
}
subT[belong].eb(i);
}
int cur, mxh = -1;
for (int i = 0; i < n_sub; ++i)
{
sort(all(subT[i]),cmp);
if (h[subT[i].back()] > mxh) mxh = h[(int)subT[i].back()], cur = i;
}
vi ans;
/*for (int i = 0; i < n_sub; ++i)
for (int x : subT[i]) ans.eb(x);*/
ans.eb(subT[cur].back());
subT[cur].pop_back();
for (int i = 1; i < n - 1; ++i)
{
if (n_sub == 3) {
mxh = -1;
for (int j = 0; j < n_sub; ++j)
if (!subT[j].empty() && h[subT[j].back()] > mxh) mxh = h[subT[j].back()];
if (!subT[cur].empty() && h[subT[cur].back()] >= mxh)
{
int mx = -1, mn = 1e9, id_mx = (cur + 1) % 3, id_mn = (cur + 2) % 3;
for (int j = 0 ; j < 3; ++j)
if (j!=cur)
{
if ((int)subT[j].size() > mx) mx = subT[j].size(), id_mx = j;
if ((int)subT[j].size() <= mn) mn = subT[j].size(), id_mn = j;
}
if (mx + 1 >= mn + (int)subT[cur].size())
{
vi vt[2];
vt[0] = subT[id_mx];
vt[1] = subT[cur];
vt[1].insert(vt[1].end(),all(subT[id_mn]));
sort(all(vt[1]),cmp);
subT[0] = vt[0];
subT[1] = vt[1];
cur = 1;
n_sub = 2;
}
} }
mxh = -1;
int nxt = cur;
for (int j = 0; j < n_sub; ++j)
if (cur != j && !subT[j].empty() && h[subT[j].back()] > mxh) mxh = h[subT[j].back()], nxt = j;
cur = nxt;
ans.eb(subT[cur].back());
subT[cur].pop_back();
}
ans.eb(root);
return ans;
}
/*int main()
{
//freopen("ss.inp", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}*/
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:56:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
56 | int cur, mxh = -1;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
336 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
336 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
336 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
134 ms |
15420 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
460 KB |
Output is correct |
21 |
Correct |
4 ms |
720 KB |
Output is correct |
22 |
Correct |
7 ms |
1272 KB |
Output is correct |
23 |
Correct |
13 ms |
2124 KB |
Output is correct |
24 |
Correct |
18 ms |
2892 KB |
Output is correct |
25 |
Correct |
78 ms |
8924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
10 ms |
1728 KB |
Output is correct |
15 |
Correct |
156 ms |
16448 KB |
Output is correct |
16 |
Correct |
155 ms |
16252 KB |
Output is correct |
17 |
Correct |
29 ms |
4036 KB |
Output is correct |
18 |
Correct |
64 ms |
7608 KB |
Output is correct |
19 |
Correct |
108 ms |
12948 KB |
Output is correct |
20 |
Correct |
5 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
336 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
336 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
336 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
134 ms |
15420 KB |
Output is correct |
45 |
Correct |
2 ms |
332 KB |
Output is correct |
46 |
Correct |
2 ms |
460 KB |
Output is correct |
47 |
Correct |
4 ms |
720 KB |
Output is correct |
48 |
Correct |
7 ms |
1272 KB |
Output is correct |
49 |
Correct |
13 ms |
2124 KB |
Output is correct |
50 |
Correct |
18 ms |
2892 KB |
Output is correct |
51 |
Correct |
78 ms |
8924 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
10 ms |
1728 KB |
Output is correct |
54 |
Correct |
156 ms |
16448 KB |
Output is correct |
55 |
Correct |
155 ms |
16252 KB |
Output is correct |
56 |
Correct |
29 ms |
4036 KB |
Output is correct |
57 |
Correct |
64 ms |
7608 KB |
Output is correct |
58 |
Correct |
108 ms |
12948 KB |
Output is correct |
59 |
Correct |
5 ms |
844 KB |
Output is correct |
60 |
Correct |
186 ms |
16508 KB |
Output is correct |
61 |
Correct |
258 ms |
18964 KB |
Output is correct |
62 |
Correct |
181 ms |
16544 KB |
Output is correct |
63 |
Correct |
216 ms |
20348 KB |
Output is correct |
64 |
Correct |
230 ms |
20452 KB |
Output is correct |
65 |
Correct |
203 ms |
16572 KB |
Output is correct |
66 |
Correct |
296 ms |
18760 KB |
Output is correct |
67 |
Correct |
247 ms |
20540 KB |
Output is correct |
68 |
Correct |
227 ms |
20052 KB |
Output is correct |
69 |
Correct |
314 ms |
21072 KB |
Output is correct |
70 |
Correct |
177 ms |
16596 KB |
Output is correct |
71 |
Correct |
241 ms |
20444 KB |
Output is correct |
72 |
Correct |
258 ms |
19208 KB |
Output is correct |
73 |
Correct |
232 ms |
20000 KB |
Output is correct |
74 |
Correct |
322 ms |
21312 KB |
Output is correct |
75 |
Correct |
209 ms |
16572 KB |
Output is correct |
76 |
Correct |
219 ms |
20396 KB |
Output is correct |
77 |
Correct |
248 ms |
20728 KB |
Output is correct |
78 |
Correct |
219 ms |
19804 KB |
Output is correct |
79 |
Correct |
261 ms |
21140 KB |
Output is correct |
80 |
Correct |
257 ms |
21340 KB |
Output is correct |
81 |
Correct |
192 ms |
16548 KB |
Output is correct |
82 |
Correct |
221 ms |
16564 KB |
Output is correct |
83 |
Correct |
214 ms |
16616 KB |
Output is correct |
84 |
Correct |
79 ms |
7088 KB |
Output is correct |