Submission #129693

#	Time	Username	Problem	Language	Result	Execution time	Memory
129693		BThero	도서관 (JOI18_library)	C++17	19 / 100	3093 ms	1008 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;

void Solve(int n) {
    vector<deque<int> > groups;
    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));
    }

    groups.pb(deque<int>({p[0]}));
    int prev = 1;

    for (int i = 1; i <= n; ++i) {
        // printf("GROUPS: %d\n", groups.size());

        // for (auto it : groups) {
        //     printf("{");

        //     for (int x : it) {
        //         printf("%d ", x);
        //     }

        //     printf("}\n");
        // }

        // printf("---\n");

        if (i == n) {
            break;
        }

        ask = vector<int>(n, 0);

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

        int cur = Query(ask);

        if (cur == prev + 1) {
            groups.pb(deque<int>({p[i]}));
        }
        else if (cur == prev) {
            for (auto &it : groups) {
                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[it.front()] = 1;

                if (Query(ask) == 1) {
                    it.push_front(p[i]);
                    break;
                }

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

                if (Query(ask) == 1) {
                    it.pb(p[i]);
                    break;
                }
            }
        }
        else {
            vector<deque<int> > tmp;
            deque<int> A, B;

            for (auto &it : groups) {
                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[it.front()] = 1;

                if (Query(ask) == 1) {
                    if (!B.empty()) {
                        reverse(all(it));
                        A = it;
                    }
                    else {
                        B = it;
                    }
                }
                else {
                    ask = vector<int>(n, 0);
                    ask[p[i]] = 1;
                    ask[it.back()] = 1;

                    if (Query(ask) == 1) {
                        if (!A.empty()) {
                            reverse(all(it));
                            B = it;
                        }
                        else {
                            A = it;
                        }
                    }
                    else {
                        tmp.pb(it);
                    }
                }
            }

            A.pb(p[i]);

            for (int x : B) {
                A.pb(x);
            }

            tmp.pb(A);
            groups = tmp;
        }

        prev = cur;
    }

    vector<int> ret;

    for (int x : groups[0]) {
        ret.pb(x + 1);
    }

	Answer(ret);
}

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