oj.uz

Submission #113278

# Submission time Handle Problem Language Result Execution time Memory
113278 2019-05-24T15:19:24 Z popovicirobert Library (JOI18_library) C++14
100 / 100
 265 ms 552 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 384 KB # of queries: 1552
2 Correct 19 ms 384 KB # of queries: 1505
3 Correct 21 ms 384 KB # of queries: 1571
4 Correct 20 ms 328 KB # of queries: 1614
5 Correct 19 ms 256 KB # of queries: 1589
6 Correct 15 ms 324 KB # of queries: 1594
7 Correct 27 ms 384 KB # of queries: 1581
8 Correct 18 ms 256 KB # of queries: 1539
9 Correct 28 ms 324 KB # of queries: 1597
10 Correct 21 ms 256 KB # of queries: 941
11 Correct 2 ms 384 KB # of queries: 1
12 Correct 1 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 2 ms 256 KB # of queries: 12
15 Correct 3 ms 384 KB # of queries: 73
16 Correct 4 ms 384 KB # of queries: 144

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 384 KB # of queries: 1552
2 Correct 19 ms 384 KB # of queries: 1505
3 Correct 21 ms 384 KB # of queries: 1571
4 Correct 20 ms 328 KB # of queries: 1614
5 Correct 19 ms 256 KB # of queries: 1589
6 Correct 15 ms 324 KB # of queries: 1594
7 Correct 27 ms 384 KB # of queries: 1581
8 Correct 18 ms 256 KB # of queries: 1539
9 Correct 28 ms 324 KB # of queries: 1597
10 Correct 21 ms 256 KB # of queries: 941
11 Correct 2 ms 384 KB # of queries: 1
12 Correct 1 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 2 ms 256 KB # of queries: 12
15 Correct 3 ms 384 KB # of queries: 73
16 Correct 4 ms 384 KB # of queries: 144
17 Correct 259 ms 552 KB # of queries: 10181
18 Correct 221 ms 376 KB # of queries: 10031
19 Correct 265 ms 384 KB # of queries: 10110
20 Correct 216 ms 384 KB # of queries: 9522
21 Correct 199 ms 380 KB # of queries: 8898
22 Correct 234 ms 424 KB # of queries: 10262
23 Correct 226 ms 380 KB # of queries: 10189
24 Correct 96 ms 340 KB # of queries: 4739
25 Correct 210 ms 484 KB # of queries: 9896
26 Correct 219 ms 428 KB # of queries: 9252
27 Correct 73 ms 336 KB # of queries: 4768
28 Correct 61 ms 352 KB # of queries: 2998
29 Correct 63 ms 352 KB # of queries: 2995
30 Correct 66 ms 368 KB # of queries: 2998