답안 #654373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654373 2022-10-31T08:07:14 Z socpite 도서관 (JOI18_library) C++17
100 / 100
316 ms 328 KB
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,sse4.2")
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef long double ld;
typedef pair<int, pair<int, int>> ftype;

const int inf = 1e9;
const int maxn = 1e3+5;

int n, ch;

vector<int> qvec;
int mm[maxn];
void Solve(int N){
    n = N;
	if(n == 1){
		Answer({1});
		return;
	}
    vector<int> re;
	vector<int> crr;
	for(int i = 1; i <= n ; i++){
		qvec.assign(n, 1);
		qvec[i-1]=0;
		if(Query(qvec) == 1){
			ch = i;
			mm[i]=1;
			break;
		}
	}
	for(int i = 0; i < n-1; i++){
		crr.clear();
		for(int j = 1; j <= n; j++)if(!mm[j])crr.push_back(j);
		int l = 0, r = crr.size()-1;
		while(l < r){
			int mid = (l+r)>>1;
			qvec.assign(n, 0);
			for(int i = l; i <= mid; i++)qvec[crr[i]-1]=1;
			qvec[ch-1]=1;
			int lt = Query(qvec);
			for(auto v: crr)qvec[v-1]^=1;
			qvec[ch-1]=0;
			int rt = Query(qvec);
			if(lt > rt)r = mid;
			else l = mid+1;
		}
		mm[crr[l]]=1;
		re.push_back(crr[l]);
	}
	re.push_back(ch);
	Answer(re);

}
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 308 KB # of queries: 2399
2 Correct 18 ms 300 KB # of queries: 2435
3 Correct 31 ms 304 KB # of queries: 2632
4 Correct 32 ms 208 KB # of queries: 2591
5 Correct 33 ms 248 KB # of queries: 2502
6 Correct 29 ms 304 KB # of queries: 2557
7 Correct 30 ms 208 KB # of queries: 2574
8 Correct 30 ms 208 KB # of queries: 2412
9 Correct 26 ms 208 KB # of queries: 2528
10 Correct 15 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 5
15 Correct 2 ms 296 KB # of queries: 75
16 Correct 4 ms 208 KB # of queries: 189
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 308 KB # of queries: 2399
2 Correct 18 ms 300 KB # of queries: 2435
3 Correct 31 ms 304 KB # of queries: 2632
4 Correct 32 ms 208 KB # of queries: 2591
5 Correct 33 ms 248 KB # of queries: 2502
6 Correct 29 ms 304 KB # of queries: 2557
7 Correct 30 ms 208 KB # of queries: 2574
8 Correct 30 ms 208 KB # of queries: 2412
9 Correct 26 ms 208 KB # of queries: 2528
10 Correct 15 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 5
15 Correct 2 ms 296 KB # of queries: 75
16 Correct 4 ms 208 KB # of queries: 189
17 Correct 289 ms 296 KB # of queries: 18036
18 Correct 257 ms 304 KB # of queries: 17243
19 Correct 316 ms 208 KB # of queries: 17467
20 Correct 261 ms 296 KB # of queries: 16297
21 Correct 200 ms 308 KB # of queries: 15346
22 Correct 304 ms 296 KB # of queries: 17601
23 Correct 302 ms 300 KB # of queries: 17174
24 Correct 141 ms 208 KB # of queries: 7891
25 Correct 302 ms 328 KB # of queries: 17096
26 Correct 211 ms 304 KB # of queries: 16015
27 Correct 103 ms 308 KB # of queries: 8016
28 Correct 214 ms 296 KB # of queries: 15957
29 Correct 183 ms 328 KB # of queries: 15939
30 Correct 226 ms 296 KB # of queries: 15957