Submission #993033

#	Time	Username	Problem	Language	Result	Execution time	Memory
993033		penguin	Library (JOI18_library)	C++17	0 / 100	32 ms	596 KiB

library

#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(b<=a); //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 (stderr)

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
• Subtask 2: 0 / 81