oj.uz

Submission #415494

# Submission time Handle Problem Language Result Execution time Memory
415494 2021-06-01T07:27:23 Z qwerasdfzxcl Library (JOI18_library) C++14
100 / 100
 609 ms 472 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
struct node{
    vector<int> a;
    int l, r;
};
vector<node> v;
vector<int> M;

void combine(int x){
    fill(M.begin(), M.end(), 0);
    M[v[0].r-1] = M[v[x].l-1] = 1;
    int tmp = Query(M);
    if (tmp==1){
        v[0].a.push_back(v[x].l);
        v[0].r = v[x].l;
        v.erase(v.begin()+x);
    }
    else{
        v[0].a.insert(v[0].a.begin(), v[x].l);
        v[0].l = v[x].l;
        v.erase(v.begin()+x);
    }
}

int bi_search(int l, int r){
    if (r-l==1) return l;
    int m = (l+r)>>1;
    fill(M.begin(), M.end(), 0);
    for (auto &x:v[0].a) M[x-1] = 1;
    for (int i=l;i<m;i++){
        for (auto &x:v[i].a) M[x-1] = 1;
    }
    int val1 = Query(M);
    for (auto &x:v[0].a) M[x-1] = 0;
    int val2 = Query(M);
    if (val1-val2==1) return bi_search(m, r);
    return bi_search(l, m);
}

void Solve(int N){
    v.resize(N);
    M.resize(N, 0);
    for (int i=0;i<N;i++){
        v[i].a.push_back(i+1);
        v[i].l = v[i].r = i+1;
    }
    for (int i=N;i>1;i--){
        int tmp = bi_search(1, i);
        combine(tmp);
    }
    Answer(v[0].a);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 200 KB # of queries: 2575
2 Correct 40 ms 200 KB # of queries: 2566
3 Correct 47 ms 200 KB # of queries: 2703
4 Correct 57 ms 292 KB # of queries: 2693
5 Correct 60 ms 200 KB # of queries: 2693
6 Correct 48 ms 200 KB # of queries: 2715
7 Correct 43 ms 200 KB # of queries: 2713
8 Correct 40 ms 284 KB # of queries: 2600
9 Correct 44 ms 200 KB # of queries: 2670
10 Correct 35 ms 200 KB # of queries: 1562
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 3 ms 200 KB # of queries: 90
16 Correct 5 ms 292 KB # of queries: 212

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 200 KB # of queries: 2575
2 Correct 40 ms 200 KB # of queries: 2566
3 Correct 47 ms 200 KB # of queries: 2703
4 Correct 57 ms 292 KB # of queries: 2693
5 Correct 60 ms 200 KB # of queries: 2693
6 Correct 48 ms 200 KB # of queries: 2715
7 Correct 43 ms 200 KB # of queries: 2713
8 Correct 40 ms 284 KB # of queries: 2600
9 Correct 44 ms 200 KB # of queries: 2670
10 Correct 35 ms 200 KB # of queries: 1562
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 3 ms 200 KB # of queries: 90
16 Correct 5 ms 292 KB # of queries: 212
17 Correct 542 ms 464 KB # of queries: 18145
18 Correct 609 ms 356 KB # of queries: 17952
19 Correct 603 ms 472 KB # of queries: 18125
20 Correct 559 ms 328 KB # of queries: 16971
21 Correct 429 ms 348 KB # of queries: 15864
22 Correct 560 ms 340 KB # of queries: 18191
23 Correct 575 ms 344 KB # of queries: 18136
24 Correct 176 ms 200 KB # of queries: 8360
25 Correct 547 ms 344 KB # of queries: 17698
26 Correct 514 ms 344 KB # of queries: 16506
27 Correct 218 ms 200 KB # of queries: 8276
28 Correct 505 ms 328 KB # of queries: 16955
29 Correct 529 ms 328 KB # of queries: 16936
30 Correct 494 ms 328 KB # of queries: 16955