Submission #113278

#	Time	Username	Problem	Language	Result	Execution time	Memory
113278		popovicirobert	Library (JOI18_library)	C++14	100 / 100	265 ms	552 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

inline void ins(vector <int> &a, vector <int> &b, int n) {
    static vector <int> cur(n, 0);

    cur[a[0]] = cur[b[0]] = 1;
    if(Query(cur) == 1) {
        cur[a[0]] = cur[b[0]] = 0;
        reverse(b.begin(), b.end());
        for(auto it : a) {
            b.push_back(it);
        }
        swap(a, b);
        return ;
    }
    cur[a[0]] = cur[b[0]] = 0;

    cur[a[0]] = cur[b.back()] = 1;
    if(Query(cur) == 1) {
        cur[a[0]] = cur[b.back()] = 0;
        for(auto it : a) {
            b.push_back(it);
        }
        swap(a, b);
        return ;
    }
    cur[a[0]] = cur[b.back()] = 0;

    cur[a.back()] = cur[b[0]] = 1;
    if(Query(cur) == 1) {
        cur[a.back()] = cur[b[0]] = 0;
        for(auto it : b) {
            a.push_back(it);
        }
        return ;
    }
    cur[a.back()] = cur[b[0]] = 0;

    reverse(b.begin(), b.end());
    for(auto it : b) {
        a.push_back(it);
    }
}

inline int get(vector < vector <int> > &segm, int sz, int n) {
    static vector <int> cur(n);

    fill(cur.begin(), cur.end(), 0);

    for(int i = 0; i <= sz; i++) {
        for(auto it : segm[i]) {
            cur[it] = 1;
        }
    }

    return Query(cur);
}


void Solve(int n) {

    vector < vector <int> > segm(n + 1);
    int sz = 0;

    vector <int> arr(n, 0);

    for(int i = 0; i < n; i++) {
        arr[i] = 1;
        int cur = Query(arr);

        if(cur == sz + 1) {
            segm[++sz].push_back(i);
        }
        else if(cur == sz) {
            segm[0] = {i};

            int res = 0;
            for(int step = 1 << 10; step; step >>= 1) {
                if(res + step <= sz && get(segm, res + step, n) == res + step + 1) {
                    res += step;
                }
            }

            res++;

            vector <int> aux = {i};

            ins(segm[res], aux, n);
        }
        else {
            segm[0] = {i};

            int a = 0, b = 0;
            for(int step = 1 << 10; step; step >>= 1) {
                if(a + step <= sz && get(segm, a + step, n) == a + step + 1) {
                    a += step;
                }
                if(b + step <= sz && get(segm, b + step, n) > b + step - 1) {
                    b += step;
                }
            }
            a++, b++;

            vector <int> aux = {i};

            ins(segm[a], aux, n);
            ins(segm[a], segm[b], n);

            for(int j = b + 1; j <= sz; j++) {
                segm[j - 1] = segm[j];
            }
            segm[sz].clear();
            sz--;
        }
    }

    for(auto &it : segm[1]) {
        it++;
    }

	Answer(segm[1]);
}

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