oj.uz

Submission #113277

# Submission time Handle Problem Language Result Execution time Memory
113277 2019-05-24T15:17:33 Z popovicirobert Library (JOI18_library) C++14
0 / 100
 299 ms 496 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 << 17; 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 << 17; 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];
            }
            sz--;
        }
    }

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

	Answer(segm[1]);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 256 KB Wrong Answer [4]
2 Incorrect 34 ms 256 KB Wrong Answer [4]
3 Incorrect 26 ms 332 KB Wrong Answer [4]
4 Incorrect 26 ms 384 KB Wrong Answer [4]
5 Incorrect 29 ms 256 KB Wrong Answer [4]
6 Incorrect 18 ms 412 KB Wrong Answer [4]
7 Incorrect 24 ms 384 KB Wrong Answer [4]
8 Incorrect 27 ms 408 KB Wrong Answer [4]
9 Incorrect 15 ms 412 KB Wrong Answer [4]
10 Incorrect 17 ms 384 KB Wrong Answer [4]
11 Correct 2 ms 384 KB # of queries: 1
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 3 ms 256 KB # of queries: 12
15 Incorrect 3 ms 256 KB Wrong Answer [4]
16 Correct 4 ms 256 KB # of queries: 144

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 256 KB Wrong Answer [4]
2 Incorrect 34 ms 256 KB Wrong Answer [4]
3 Incorrect 26 ms 332 KB Wrong Answer [4]
4 Incorrect 26 ms 384 KB Wrong Answer [4]
5 Incorrect 29 ms 256 KB Wrong Answer [4]
6 Incorrect 18 ms 412 KB Wrong Answer [4]
7 Incorrect 24 ms 384 KB Wrong Answer [4]
8 Incorrect 27 ms 408 KB Wrong Answer [4]
9 Incorrect 15 ms 412 KB Wrong Answer [4]
10 Incorrect 17 ms 384 KB Wrong Answer [4]
11 Correct 2 ms 384 KB # of queries: 1
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 3 ms 256 KB # of queries: 12
15 Incorrect 3 ms 256 KB Wrong Answer [4]
16 Correct 4 ms 256 KB # of queries: 144
17 Incorrect 239 ms 380 KB Wrong Answer [4]
18 Incorrect 297 ms 496 KB Wrong Answer [4]
19 Incorrect 269 ms 424 KB Wrong Answer [4]
20 Incorrect 249 ms 256 KB Wrong Answer [4]
21 Incorrect 181 ms 476 KB Wrong Answer [4]
22 Incorrect 299 ms 376 KB Wrong Answer [4]
23 Incorrect 282 ms 356 KB Wrong Answer [4]
24 Incorrect 68 ms 456 KB Wrong Answer [4]
25 Incorrect 263 ms 380 KB Wrong Answer [4]
26 Incorrect 239 ms 432 KB Wrong Answer [4]
27 Incorrect 96 ms 376 KB Wrong Answer [4]
28 Correct 82 ms 256 KB # of queries: 2998
29 Correct 67 ms 384 KB # of queries: 2995
30 Correct 71 ms 384 KB # of queries: 2998