oj.uz

답안 #96719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96719 2019-02-11T12:26:09 Z Retro3014 도서관 (JOI18_library) C++17
100 / 100
 525 ms 404 KB 
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>

#include "library.h"

using namespace std;

int q(const vector<int>& M){
	for(int i=0; i<M.size(); i++){
		if(M[i]!=0){
			return Query(M);
		}
	}return 0;
}


void Solve(int N){	
	vector<int> v(N);
	vector<int> ans(N);
	vector<bool> chk(N, 0);
	vector<int> idx(N);
	for(int i=0; i<N; i++){
		v[i] = true;
		idx[i] = i;
	}
	for(int i=0; i<N; i++){
		v[i] = false;
		int k = q(v);
		v[i] = true;
		if(k==1){
			ans[0] = i;
			idx[i] = N;
			chk[i] = true;
			break;
		}
	}
	for(int i=1; i<N; i++){
		sort(idx.begin(), idx.end());
		idx.pop_back();
		int s = 0, e = idx.size()-1, m;
		while(s<e){
			m = (s+e)/2;
			int k1, k2;
			for(int j=0; j<N; j++){
				if(chk[j]){
					v[j] = false;
				}else if(idx[s]<=j && j<=idx[m]){
					v[j] = true;
				}else{
					v[j] = false;
				}
			}
			k1 = q(v);
			for(int j=0; j<N; j++){
				if(chk[j]){
					v[j] = true;
				}else if(idx[s]<=j && j<=idx[m]){
					v[j] = true;
				}else{
					v[j] = false;
				}
			}
			k2 = q(v);
			if(k1==k2){
				e = m;
			}else{
				s = m+1;
			}
		}
		ans[i] = idx[s];
		chk[idx[s]] = true;
		idx[s] = N;
	}
	for(int i=0; i<N; i++){
		ans[i]++;
	//	cout<<ans[i]<<' '<<endl;
	}
	Answer(ans);
	return;
}

Compilation message

library.cpp: In function 'int q(const std::vector<int>&)':
library.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<M.size(); i++){
               ~^~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 376 KB # of queries: 2387
2 Correct 40 ms 376 KB # of queries: 2433
3 Correct 50 ms 248 KB # of queries: 2638
4 Correct 33 ms 248 KB # of queries: 2593
5 Correct 38 ms 376 KB # of queries: 2504
6 Correct 40 ms 376 KB # of queries: 2553
7 Correct 60 ms 376 KB # of queries: 2568
8 Correct 40 ms 376 KB # of queries: 2402
9 Correct 42 ms 248 KB # of queries: 2512
10 Correct 25 ms 404 KB # of queries: 1478
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 1
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 73
16 Correct 4 ms 376 KB # of queries: 187

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 376 KB # of queries: 2387
2 Correct 40 ms 376 KB # of queries: 2433
3 Correct 50 ms 248 KB # of queries: 2638
4 Correct 33 ms 248 KB # of queries: 2593
5 Correct 38 ms 376 KB # of queries: 2504
6 Correct 40 ms 376 KB # of queries: 2553
7 Correct 60 ms 376 KB # of queries: 2568
8 Correct 40 ms 376 KB # of queries: 2402
9 Correct 42 ms 248 KB # of queries: 2512
10 Correct 25 ms 404 KB # of queries: 1478
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 1
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 73
16 Correct 4 ms 376 KB # of queries: 187
17 Correct 470 ms 248 KB # of queries: 18008
18 Correct 448 ms 248 KB # of queries: 17231
19 Correct 525 ms 248 KB # of queries: 17451
20 Correct 442 ms 248 KB # of queries: 16277
21 Correct 346 ms 248 KB # of queries: 15362
22 Correct 518 ms 248 KB # of queries: 17617
23 Correct 452 ms 248 KB # of queries: 17170
24 Correct 188 ms 248 KB # of queries: 7885
25 Correct 487 ms 248 KB # of queries: 17118
26 Correct 415 ms 248 KB # of queries: 15989
27 Correct 177 ms 248 KB # of queries: 7994
28 Correct 492 ms 376 KB # of queries: 17935
29 Correct 467 ms 376 KB # of queries: 17915
30 Correct 494 ms 376 KB # of queries: 17935