Submission #129735

#	Time	Username	Problem	Language	Result	Execution time	Memory
129735		BThero	Library (JOI18_library)	C++17	100 / 100	275 ms	636 KiB

library

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "library.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e3 + 5;

vector<int> V[MAXN], S;

int par[MAXN];

int getPar(int x) {
    if (x == par[x]) {
        return x;
    }
    else {
        return par[x] = getPar(par[x]);
    }
}

void uni(int a, int b) {
    a = getPar(a);
    b = getPar(b);

    if (a == b) {
        return;
    }

    par[b] = a;

    for (int x : V[b]) {
        V[a].pb(x);
    }

    V[b].clear();
    int p = 0;

    while (S[p] != b) {
        ++p;
    }

    S.erase(S.begin() + p);
}

void Solve(int n) {
    vector<int> ask, p(n);

    for (int i = 0; i < n; ++i) {
        p[i] = i;
    }

    for (int step = 0; step < 10; ++step) {
        random_shuffle(all(p));
    }

    for (int i = 0; i < n; ++i) {
        par[i] = i;
        V[i].pb(i);
    }

    S.pb(p[0]);
    int prev = 1;

    for (int i = 1; i < n; ++i) {
        ask = vector<int>(n, 0);

        for (int j = 0; j <= i; ++j) {
            ask[p[j]] = 1;
        }

        int cur = Query(ask);
        S.pb(p[i]);
        
        if (cur == prev) {
            vector<int> T;

            for (int x : S) {
                if (x != p[i]) {
                    T.pb(x);
                }
            }

            while (T.size() > 1) {
                vector<int> tmp;

                for (int j = 0; j < T.size() / 2; ++j) {
                    tmp.pb(T[j]);
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) != need) {
                    tmp.clear();

                    for (int j = T.size() / 2; j < T.size(); ++j) {
                        tmp.pb(T[j]);
                    }
                }
                
                T = tmp;
            }

            ask = vector<int>(n, 0);
            ask[p[i]] = 1;
            ask[V[T[0]].front()] = 1;

            if (Query(ask) == 1) {
                uni(p[i], T[0]);
            }
            else {
                uni(T[0], p[i]);
            }
        }
        else if (cur == prev - 1) {
            int a = -1, b = -1;
            vector<int> T;

            for (int x : S) {
                if (x != p[i]) {
                    T.pb(x);
                }
            }

            while (T.size() > 1) {
                vector<int> tmp;

                for (int j = 0; j < T.size() / 2; ++j) {
                    tmp.pb(T[j]);
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) > need) {
                    tmp.clear();

                    for (int j = T.size() / 2; j < T.size(); ++j) {
                        tmp.pb(T[j]);
                    }
                }
                
                T = tmp;
            }

            ask = vector<int>(n, 0);
            ask[p[i]] = 1;
            ask[V[T[0]].front()] = 1;

            if (Query(ask) == 1) {
                b = T[0];
            }
            else {
                a = T[0];
            }

            T.clear();

            for (int x : S) {
                if (x != a && x != b && x != p[i]) {
                    T.pb(x);
                }
            }

            while (T.size() > 1) {
                vector<int> tmp;

                for (int j = 0; j < T.size() / 2; ++j) {
                    tmp.pb(T[j]);
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) > need) {
                    tmp.clear();

                    for (int j = T.size() / 2; j < T.size(); ++j) {
                        tmp.pb(T[j]);
                    }
                }
                
                T = tmp;
            }

            ask = vector<int>(n, 0);
            ask[p[i]] = 1;
            ask[V[T[0]].front()] = 1;

            if (Query(ask) == 1) {
                if (b != -1) {
                    reverse(all(V[T[0]]));
                    a = T[0];
                }
                else {
                    b = T[0];
                }
            }
            else {
                if (a != -1) {
                    reverse(all(V[T[0]]));
                    b = T[0];
                }
                else {
                    a = T[0];
                }
            }

            uni(a, p[i]);
            uni(p[i], b);
        }

        prev = cur;
    }

    int v = 0;

    while (getPar(v) != v) {
        ++v;
    }

    for (int &x : V[v]) {
        ++x;
    }

	Answer(V[v]);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:106:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:129:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~
library.cpp:161:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:184:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~
library.cpp:214:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:237:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~

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