Submission #823878

#	Time	Username	Problem	Language	Result	Execution time	Memory
823878		Kahou	Library (JOI18_library)	C++14	100 / 100	210 ms	1076 KiB

library

#include<bits/stdc++.h>
#include"library.h"
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1050;
int n;
deque<int> dq[MAXN];

vector<int> get(int k) {
        vector<int> out(n);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
                if (dq[i].empty()) continue;
                cnt++;
                if (cnt > k) break;
                for (int x:dq[i]) {
                        out[x-1] = 1;
                }
        }
        return out;
}
int getid(int x) {
        for (int i = 1; i <= n; i++) {
                if (dq[i].empty()) continue;
                x--;
                if (!x) return i;
        }
        return 0;
}

void Solve(int N) {
        n = N;
        int t = 1;
        dq[1].push_back(1);
        vector<int> vc(n);
        for (int i = 2; i <= n; i++) {
                vc = get(t);
                vc[i-1] = 1;
                int nt = Query(vc);
                if (nt > t) {
                        dq[i].push_back(i);
                        t++;
                }
                else if (nt == t) {
                        int dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) > md) dw = md;
                                else up = md;
                        }
                        int id = getid(up);
                        bool flg = 0;
                        if (dq[id].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x:dq[id]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[id].back()-1] = 0;
                                flg = (Query(vc) > 1);
                        }
                        if (flg) dq[id].push_back(i);
                        else dq[id].push_front(i);
                }
                else if (nt < t) {
                        int dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) > md) dw = md;
                                else up = md;
                        }
                        int A = getid(up);
                        dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) >= md) dw = md;
                                else up = md;
                        }
                        int B = getid(up);

                        bool flgA = 0, flgB = 0;
                        if (dq[A].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x : dq[A]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[A].back()-1] = 0;
                                flgA = (Query(vc) > 1);
                        }
                        if (dq[B].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x : dq[B]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[B].back()-1] = 0;
                                flgB = (Query(vc) > 1);
                        }

                        if (flgA) dq[A].push_back(i);
                        else dq[A].push_front(i);

                        if (flgB) reverse(dq[B].begin(), dq[B].end());
                        for (int x:dq[B]) {
                                if (flgA) dq[A].push_back(x);
                                else dq[A].push_front(x);
                        }
                        dq[B].clear();
                        t--;
                }
        }

        vector<int> out;
        for (int x:dq[1]) {
                out.push_back(x);
        }
        Answer(out);
}

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