Submission #935526

# Submission time Handle Problem Language Result Execution time Memory
935526 2024-02-29T08:47:09 Z yhkhoo Library (JOI18_library) C++17
0 / 100
24 ms 440 KB
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

void Solve(int N){
	vector<int> res(N);
	vector<int> m0(N, 1);
	int le=-1, re=-1;
	for(int i=0; i<N; i++){
		if(i != 0){
			m0[i-1] = 1;
		}
		m0[i] = 0;
		if(Query(m0) == 1){
			if(le == -1){
				le = i;
			}
			else{
				re = i;
			}
		}
	}
	vector<int> cons(N);
	for(int i=0; i<N; i++){
		cons[i] = i;
	}
	cons.erase(lower_bound(cons.begin(), cons.end(), le));
	cons.erase(lower_bound(cons.begin(), cons.end(), re));
	res[0] = le;
	res[N-1] = re;
	for(int i=1; i<N-1; i++){
		int l = 0, r = cons.size()-1, m;
		while(l < r){
			m = (l+r)/2;
			vector<int> m1(N, 0);
			for(int i=l; i<=m; i++){
				m1[cons[i]] = 1;
			}
			m1[res[i-1]] = 1;
			auto wit = Query(m1);
			m1[res[i-1]] = 0;
			auto wito = Query(m1);
			if(wito == wit){ // is in
				r = m;
			}
			else{ // not in
				l = m+1;
			}
		}
		res[i] = cons[l];
		cons.erase(cons.begin()+l);
	}
	for(int i=0; i<N; i++){
		res[i]++;
	}
	Answer(res);
}
# Verdict Execution time Memory Grader output
1 Correct 17 ms 436 KB # of queries: 2540
2 Correct 17 ms 440 KB # of queries: 2533
3 Correct 22 ms 436 KB # of queries: 2678
4 Correct 24 ms 436 KB # of queries: 2680
5 Correct 21 ms 432 KB # of queries: 2678
6 Correct 21 ms 432 KB # of queries: 2670
7 Correct 23 ms 440 KB # of queries: 2694
8 Correct 16 ms 436 KB # of queries: 2551
9 Correct 20 ms 428 KB # of queries: 2653
10 Correct 11 ms 432 KB # of queries: 1563
11 Runtime error 1 ms 436 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 17 ms 436 KB # of queries: 2540
2 Correct 17 ms 440 KB # of queries: 2533
3 Correct 22 ms 436 KB # of queries: 2678
4 Correct 24 ms 436 KB # of queries: 2680
5 Correct 21 ms 432 KB # of queries: 2678
6 Correct 21 ms 432 KB # of queries: 2670
7 Correct 23 ms 440 KB # of queries: 2694
8 Correct 16 ms 436 KB # of queries: 2551
9 Correct 20 ms 428 KB # of queries: 2653
10 Correct 11 ms 432 KB # of queries: 1563
11 Runtime error 1 ms 436 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -