이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "fun.h"
using namespace std;
#define pb push_back
int fast_pow(int a, int b)
{
if(b==0)
return 1;
int u = fast_pow(a, b/2);
u = u*u;
if(b%2==1)
u*=a;
return u;
}
vector<int> createFunTour(int n, int q)
{
if(n<=500)
{
vector<vector<int>> dist(n, vector<int>(n, 0));
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
dist[i][j] = hoursRequired(i, j);
}
}
int u = 0;
int ma = 0;
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
if(dist[i][j]>ma)
{
ma = dist[i][j];
u = i;
}
}
}
vector<bool> visited(n, false);
vector<int> res;
while((int)res.size()<n)
{
res.pb(u);
visited[u] = true;
int maxi = 0;
int v = 0;
for(int i = 0; i<n; i++)
{
if(visited[i])
continue;
if(dist[u][i]>maxi)
{
v = i;
maxi = dist[u][i];
}
}
u = v;
}
return res;
}
else
{
int ptr1, ptr2, pow1, pow2;
int deg = 0;
int temp = n+1;
while(temp>1)
{
temp/=2;
deg++;
}
if(n-1>=fast_pow(2, deg) + fast_pow(2, deg-1)-1)
{
ptr2 = n-1;
ptr1 = fast_pow(2, deg) + fast_pow(2, deg-1)-2;
pow1 = deg, pow2 = deg;
}
else
{
ptr2 = fast_pow(2, deg) -2;
pow2 = deg-1;
ptr1 = n-1;
pow1 = deg;
}
vector<int> res;
bool flag = true;
while((int)res.size()<n)
{
if(flag)
{
res.pb(ptr1);
ptr1--;
if(ptr1==fast_pow(2, pow1)-2)
{
pow1--;
ptr1 = fast_pow(2, pow1) + fast_pow(2, pow1-1) -2;
}
}
else
{
if(ptr2<0)
{
flag = !flag;
continue;
}
res.pb(ptr2);
ptr2--;
if(ptr2==fast_pow(2, pow2) + fast_pow(2, pow2-1)-2)
{
ptr2 = fast_pow(2, pow2) -2 ;
pow2--;
}
}
flag = !flag;
}
return res;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |