Submission #1215086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215086		og_matveychick1	Library (JOI18_library)	C++20	100 / 100	222 ms	804 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
#include "bits/stdc++.h"

using namespace std;

const int N = 1e3 + 5;
int n;
vector<int> g[N];

int f(vector<pair<vector<int>, int>> p) {
    vector<int> q(n);
    for (auto a: p) for (auto x: a.first) q[x] = 1;
    return Query(q);
}

int f(vector<int> a, vector<int> b) {
    vector<int> q(n);
    for (auto x: a) q[x] = 1;
    for (auto x: b) q[x] = 1;
    return Query(q);
}

int f(int x, int y) {
    vector<int> q(n);
    q[x] = q[y] = 1;
    return Query(q);
}

vector<int> go(vector<pair<vector<int>, int>> a) {
    if (a.size() == 1) return {0};
    vector<int> cmp(a.size(), -1), st(n);
    for (int i = 0; i < a.size(); i++) for (auto x: a[i].first) st[x] = a[i].second;
    vector<pair<vector<int>, int>> p, d;
    for (int i = 0; i < a.size(); i++) {
        p.push_back({a[i].first, p.size()});
        if (f(p) != p.size()) p.pop_back();
        else cmp[i] = p.size() - 1;
    }
    d.resize(p.size());
    for (int i = 0; i < a.size(); i++) {
        if (cmp[i] != -1) continue;
        int l = 0, r = p.size();
        while (l + 1 < r) {
            int c = (l + r) / 2;
            auto p1 = p;
            p1.resize(c);
            p1.push_back({a[i].first, 0});
            (f(p1) < p1.size() ? r : l) = c;
        }
        cmp[i] = l;
        for (auto x: a[i].first) d[l].first.push_back(x);
    }
    for (int i = 0; i < d.size(); i++) for (auto x: d[i].first) p[i].first.push_back(x);
    auto rc = go(p);
    vector<pair<vector<int>, int>> _p(p.size());
    for (int i = 0; i < p.size(); i++) _p[rc[i]] = p[i];
    swap(_p, p);
    vector<vector<int>> id(p.size());
    for (int i = 0; i < p.size(); i++) {
        for (auto x: p[i].first) id[i].push_back(st[x]);
        sort(id[i].begin(), id[i].end());
        id[i].resize(unique(id[i].begin(), id[i].end()) - id[i].begin());
    }
    vector<vector<pair<vector<int>, int>>> b(p.size());
    for (int i = 0; i < p.size(); i++) for (auto x: id[i]) b[i].push_back(a[x]);
    for (int i = 0; i < b.size(); i++) {
        if (b[i].size() != 3) continue;
        int c0 = f(b[i][1].first, b[i][0].first);
        int c2 = f(b[i][1].first, b[i][2].first);
        if (c0 == 1 && c2 == 1);
        else {
            if (c0 == 2) swap(b[i][1], b[i][2]);
            else swap(b[i][1], b[i][0]);
        }
    }
    if (b.size() > 1) {
        if (f(b[0][0].first, b[1][0].first) == 1 ||
            f(b[0][0].first, b[1][b[1].size() - 1].first) == 1) {
            reverse(b[0].begin(), b[0].end());
        }
    }
    for (int i = 1; i < b.size(); i++) {
        if (f(b[i][b[i].size() - 1].first, b[i - 1][b[i - 1].size() - 1].first) == 1) {
            reverse(b[i].begin(), b[i].end());
        }
    }
    vector<int> rt(a.size());
    int it = 0;
    for (int i = 0; i < b.size(); i++) for (auto x: b[i]) rt[x.second] = it++;
    return rt;
}

void Solve(int _n) {
    n = _n;
    vector<pair<vector<int>, int>> p(n);
    for (int i = 0; i < n; i++) p[i] = {{i}, i};
    auto rc = go(p);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[rc[i]] = i + 1;
    Answer(ans);
}

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