| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 394186 |
2021-04-26T04:17:51 Z |
IloveN |
Fun Tour (APIO20_fun) |
C++14 |
|
1 ms |
204 KB |
#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]));
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]));
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Tour is not fun |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Tour is not fun |
| # |
Verdict |
Execution time |
Memory |
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 |
Incorrect |
1 ms |
204 KB |
Tour is not fun |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Tour is not fun |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Tour is not fun |
