oj.uz

Submission #993022

# Submission time Handle Problem Language Result Execution time Memory
993022 2024-06-05T09:01:05 Z penguin Library (JOI18_library) C++17
0 / 100
 35 ms 344 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;
    //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:54:21: warning: 'left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |             if(check(lower, mid, left)) upper = mid;
      |                ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB # of queries: 2749
2 Correct 31 ms 344 KB # of queries: 2787
3 Correct 22 ms 340 KB # of queries: 3004
4 Correct 29 ms 344 KB # of queries: 2921
5 Correct 30 ms 344 KB # of queries: 2868
6 Correct 26 ms 344 KB # of queries: 2919
7 Correct 32 ms 344 KB # of queries: 2908
8 Correct 28 ms 344 KB # of queries: 2742
9 Correct 35 ms 344 KB # of queries: 2880
10 Correct 16 ms 344 KB # of queries: 1628
11 Runtime error 1 ms 344 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB # of queries: 2749
2 Correct 31 ms 344 KB # of queries: 2787
3 Correct 22 ms 340 KB # of queries: 3004
4 Correct 29 ms 344 KB # of queries: 2921
5 Correct 30 ms 344 KB # of queries: 2868
6 Correct 26 ms 344 KB # of queries: 2919
7 Correct 32 ms 344 KB # of queries: 2908
8 Correct 28 ms 344 KB # of queries: 2742
9 Correct 35 ms 344 KB # of queries: 2880
10 Correct 16 ms 344 KB # of queries: 1628
11 Runtime error 1 ms 344 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -