Submission #1176431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176431		nguyn	Library (JOI18_library)	C++20	100 / 100	118 ms	504 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
#define pb push_back
using namespace std;

int n;
vector<int> m;
vector<int> vis;
vector<int> g[1005];

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v] || !m[v - 1]) continue;
        dfs(v);
    }
}

int cal(vector<int> &m) {
    int comp = 0;
    vis.assign(n + 3, 0);
    for (int i = 0; i < m.size(); i++) {
        if (!vis[i + 1] && m[i] == 1) {
            comp++;
            dfs(i + 1);
        }
    }
    return comp;
}

int h[1005];
void trace(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v]) continue;
        h[v] = h[u] + 1;
        trace(v);
    }
}

void Solve(int N) {
    n = N;
    if (n == 1 || n == 2) {
        vector<int> res;
        for (int i = 1; i <= n; i++) res.pb(i);
        Answer(res);
        return;
    }
    m.resize(n);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j <= i) m[j - 1] = 1;
            else m[j - 1] = 0;
        }
        while (Query(m) < cal(m)) {
            int l = 1;
            int r = i - 1;
            int ans = 0;
            while(l <= r) {
                int mid = (l + r) / 2;
                for (int j = 1; j <= n; j++) {
                    if (j <= i && j >= mid) m[j - 1] = 1;
                    else m[j - 1] = 0;
                }
//                for (int i : m) cout << i << ' ';
//                cout << endl;
//                cout << Query(m) << ' ' << cal(m) << endl;
                if (Query(m) < cal(m)) {
                    l = mid + 1;
                    ans = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            g[ans].pb(i);
            g[i].pb(ans);
            for (int j = 1; j <= n; j++) {
                if (j <= i) m[j - 1] = 1;
                else m[j - 1] = 0;
            }
//            cout << ans << ' ' << i << endl;
        }
    }
    vis.assign(n + 1, 0);
    trace(1);
    int best = 1;
    for (int i = 1; i <= n; i++) {
        if (h[best] < h[i]) best = i;
    }
//    cout << "sech" << endl;
    h[best] = 0;
    vis.assign(n + 1, 0);
    trace(best);
    vector<int> res(n);
    for (int i = 1; i <= n; i++) {
        res[h[i]] = i;
    }
//    for (int i : res) {
//        cout << i << ' ';
//    }
    Answer(res);

}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81