oj.uz

Submission #993571

# Submission time Handle Problem Language Result Execution time Memory
993571 2024-06-06T05:08:35 Z penguin Library (JOI18_library) C++17
100 / 100
 247 ms 848 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
// #define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define nl "\n"

int n;
set<int> s;

bool check(int l, int m, int e){
    vector<int> v(n, 0);
    bool empty = true;
    for (int i=l; i<=m; i++){
        if(s.find(i)!=s.end()){
            empty = false;
            v[i-1]=1;
        }
    }
    if(empty==true) return false;
    int a = Query(v);
    v[e-1] = 1;
    int b = Query(v);
    return(a==b); //includes desired
}

void Solve(int N){
    n = N;
    vector<int> M(N);
    vector<int> res;
    if(N==1){
        Answer({1});
        return;
    }
    //books are 1-indexed
	for(int i=0; i<N; i++) {
		M[i] = 1;
        s.insert(i+1);
	}
    int firstbook;
    for (int i=0; i<N; i++){
        if(i>0) M[i-1]=1;
        M[i] = 0;
        int fb = Query(M);
        if(fb==1){
            res.push_back(i+1);
            s.erase(i+1);
            firstbook = i+1;
            break;
        }
    }
    int left = firstbook;
    for (int i=1; i<N; i++){
        int lower = 1;
        int upper = N;
        while(upper-lower>0){
            int mid = (upper+lower)/2;
            if(check(lower, mid, left)) upper = mid;
            else lower = mid+1;
        }
        // lower is next book in line
        res.push_back(lower);
        s.erase(lower);
        left = lower;
    }
    Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:58:21: warning: 'left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |             if(check(lower, mid, left)) upper = mid;
      |                ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB # of queries: 2749
2 Correct 23 ms 344 KB # of queries: 2787
3 Correct 40 ms 344 KB # of queries: 3004
4 Correct 22 ms 344 KB # of queries: 2921
5 Correct 23 ms 344 KB # of queries: 2868
6 Correct 21 ms 344 KB # of queries: 2919
7 Correct 24 ms 344 KB # of queries: 2908
8 Correct 35 ms 344 KB # of queries: 2742
9 Correct 25 ms 344 KB # of queries: 2880
10 Correct 16 ms 344 KB # of queries: 1628
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 91
16 Correct 3 ms 344 KB # of queries: 231

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB # of queries: 2749
2 Correct 23 ms 344 KB # of queries: 2787
3 Correct 40 ms 344 KB # of queries: 3004
4 Correct 22 ms 344 KB # of queries: 2921
5 Correct 23 ms 344 KB # of queries: 2868
6 Correct 21 ms 344 KB # of queries: 2919
7 Correct 24 ms 344 KB # of queries: 2908
8 Correct 35 ms 344 KB # of queries: 2742
9 Correct 25 ms 344 KB # of queries: 2880
10 Correct 16 ms 344 KB # of queries: 1628
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 91
16 Correct 3 ms 344 KB # of queries: 231
17 Correct 247 ms 484 KB # of queries: 19548
18 Correct 222 ms 472 KB # of queries: 18781
19 Correct 239 ms 476 KB # of queries: 18931
20 Correct 212 ms 848 KB # of queries: 17933
21 Correct 192 ms 468 KB # of queries: 16904
22 Correct 226 ms 344 KB # of queries: 19157
23 Correct 229 ms 472 KB # of queries: 18738
24 Correct 95 ms 592 KB # of queries: 8615
25 Correct 211 ms 464 KB # of queries: 18634
26 Correct 217 ms 596 KB # of queries: 17475
27 Correct 79 ms 436 KB # of queries: 8856
28 Correct 114 ms 344 KB # of queries: 10069
29 Correct 105 ms 344 KB # of queries: 10063
30 Correct 114 ms 344 KB # of queries: 10069