Submission #72365

#	Time	Username	Problem	Language	Result	Execution time	Memory
72365		IDxTree (#118)	Key of Impassable Doors (FXCUP3_key)	C++17	100 / 100	41 ms	4676 KiB

key

#include "key.h"
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int isz[1001];
vector<int> ord[1001];
int nxt[1001];
int msy[1001];

namespace uf {
    int par[1001];
    int cyc[1001];
    int sz[1001];
    int find(int x) {
        if (par[x]) return par[x] = find(par[x]);
        return x;
    }
    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        if (sz[x] < sz[y]) swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        return 1;
    }
}

int ch[1001];
int dfs(int x) {
    x = uf::find(x);
    if (ch[x]) return 0;
    ch[x] = 1;
    if (nxt[x]) return dfs(nxt[x]) + 1;
    return isz[x];
}

int bsearch(vector<int> &ord, int x, int s, int e) {
    if (s > e) return 0;
    int sz = 1;
    for (int i = 1; i <= n; ++i) ch[i] =  0;
    for (int i = s; i <= e; ++i) {
        sz += dfs(ord[i]);
        TakeKey(ord[i]);
    }
    TakeKey(x);
    int ret = Explore();
    return ret == sz;
}

int cycsearch(vector<int> &cyc, int x) {
    int s = 0, e = cyc.size();
    while (s < e) {
        int m = (s + e) / 2;
        for (int i = s; i <= m; ++i) TakeKey(cyc[i]);
        TakeKey(x);
        int ret = Explore();
        if (ret == (m - s + 1) * isz[x]) e = m;
        else s = m + 1;
    }
    return s;
}

void EnsureKeyInfo(int N) {
    n = N;
    for (int i = 1; i <= n; ++i) {
        TakeKey(i); ord[isz[i] = Explore()].push_back(i);
        uf::sz[i] = 1;
    }
    vector<int> pr, tp;
    for (int it = 1; it <= n; ++it) {
        vector<int> res;
        for (int i : ord[it]) {
            int s = 0, e = pr.size();
            while (s < e) {
                int m = (s + e) / 2;
                if (bsearch(pr, i, s, m)) e = m;
                else s = m + 1;
            }
            if (s != pr.size()) nxt[i] = pr[s], msy[i] = msy[pr[s]], tp.push_back(i);
            else res.push_back(i);
        }
        vector<int> cyc;
        for (int i : res) {
            int ret = cycsearch(cyc, i);
            if (ret != cyc.size()) uf::merge(cyc[ret], i), msy[i] = msy[cyc[ret]];
            else cyc.push_back(i), tp.push_back(i), msy[i] = i;
        }
        pr = tp;
        tp.clear();
    }
    
    for (int i = 1; i <= n; ++i) {
        int x = i;
        while (nxt[x]) {
            Report(i, x);
            x = nxt[x];
        }
        for (int j = 1; j <= n; ++j) {
            if (nxt[j]) continue;
            if (uf::find(msy[i]) == uf::find(j)) Report(i, j);
        }
    }
}

Compilation message (stderr)

key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (s != pr.size()) nxt[i] = pr[s], msy[i] = msy[pr[s]], tp.push_back(i);
                 ~~^~~~~~~~~~~~
key.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ret != cyc.size()) uf::merge(cyc[ret], i), msy[i] = msy[cyc[ret]];
                 ~~~~^~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 34 / 34
• Subtask 3: 43 / 43