Submission #729019

#	Time	Username	Problem	Language	Result	Execution time	Memory
729019		stevancv	Fun Tour (APIO20_fun)	C++14	26 / 100	16 ms	2772 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 2e9;
vector<int> graf[N];
deque<int> dq[21];
int mxd;
void Dfs(int s, int t) {
    smax(mxd, t);
    dq[t].push_back(s);
    for (int u : graf[s]) {
        Dfs(u, t + 1);
    }
}
vector<int> createFunTour(int n, int q) {
    if (n <= 500) {
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (hoursRequired(i, j) == 1) {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        vector<int> ans;
        vector<int> bia(n);
        int tko = 0;
        while (ans.size() < n) {
            queue<int> q;
            vector<int> dist(n, inf);
            q.push(tko);
            dist[tko] = 0;
            while (!q.empty()) {
                int s = q.front(); q.pop();
                for (int u : g[s]) {
                    if (dist[u] > dist[s] + 1) {
                        dist[u] = dist[s] + 1;
                        q.push(u);
                    }
                }
            }
            int mx = tko;
            for (int i = 0; i < n; i++) {
                if (bia[i] == 0 && dist[i] > dist[mx]) mx = i;
            }
            ans.push_back(mx);
            bia[mx] = 1;
            tko = mx;
        }
        return ans;
    }
    for (int i = 1; i < n; i++) {
        int p = (i - 1) / 2;
        graf[p].push_back(i);
    }
    Dfs(0, 0);
    int gdi = min((int)dq[mxd].size(), 1 << (mxd - 1));
    for (int z = 0; z < gdi; z++) {
        dq[mxd - 1].push_front(dq[mxd].front());
        dq[mxd].pop_front();
    }
    while (!dq[mxd].empty()) {
        dq[mxd - 1].push_back(dq[mxd].back());
        dq[mxd].pop_back();
    }
    vector<int> ans;
    int poc = 1;
    for (int i = mxd - 1; i >= 0; i--) {
        while (!dq[i].empty()) {
            if (poc == 1) {
                ans.push_back(dq[i].front());
                dq[i].pop_front();
            }
            else {
                ans.push_back(dq[i].back());
                dq[i].pop_back();
            }
            poc ^= 1;
        }
    }
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:36:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while (ans.size() < n) {
      |                ~~~~~~~~~~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34