답안 #950955

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950955 2024-03-21T03:07:56 Z phoenix0423 도서관 (JOI18_library) C++17
100 / 100
739 ms 1492 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
// #define int long long
#define lowbit(x) x&-x
const int maxn = 1005;
#include "library.h"
int n;
vector<int> adj[maxn];
vector<pll> edge;

int con(vector<int> a){
    set<int> cur;
    for(auto x : a) cur.insert(x);
    int cnt = 0;
    for(auto [a, b] : edge) if(cur.count(a) && cur.count(b)) cnt++;
    return cnt;
}

int qry(vector<int> a){
	// cout<<"q : ";
	// for(auto x : a) cout<<x<<" ";
	// cout<<"\n";
	// int op;
	// cin>>op;
    // cout<<"con : "<<con(a)<<"\n";
	// return op < int(a.size()) - con(a);
	vector<int> cur(n);
	for(auto x : a) cur[x - 1] = 1;
	int op = Query(cur);
	return op < int(a.size()) - con(a);
}
void add(int a, int b){
	adj[a].pb(b);
	adj[b].pb(a);
    edge.eb(a, b);
}

void Solve(int _n){
	n = _n;
	vector<int> q;
	for(int rd = 0; rd < n - 1; rd++){
		vector<int> cand;
		for(int j = 1; j <= n; j++) cand.pb(j);
		int l = 0, r = cand.size() - 1;
		while(l + 1 < r){
            // cout<<"bs : "<<l<<" "<<r<<"\n";
			int m = (l + r) / 2;
			vector<int> a, b;
			for(int i = l; i <= m; i++) a.pb(cand[i]);
			for(int i = m + 1; i <= r; i++) b.pb(cand[i]);
			if(qry(a)) r = m;
			else if(qry(b)) l = m + 1;
			else break;
		}
		if(r == l + 1){
			add(cand[l], cand[r]);
			continue;
		}
		int m = (l + r) / 2;
		int L = l, R = m;
		while(L < R){
			int mid = (L + R) / 2;
			vector<int> a;
			for(int i = m + 1; i <= r; i++) a.pb(cand[i]);
			for(int i = L; i <= mid; i++) a.pb(cand[i]);
			if(qry(a)) R = mid;
			else L = mid + 1;
		}
		int fr = cand[L];
		L = m + 1, R = r;
		while(L < R){
			int mid = (L + R) / 2;
			vector<int> a;
			a.pb(fr);
			for(int i = L; i <= mid; i++) a.pb(cand[i]);
			if(qry(a)) R = mid;
			else L = mid + 1;
		}
		add(fr, cand[L]);
	}
	int pos = 1;
	for(int i = 1; i <= n; i++){
		if(adj[i].size() == 1){
			pos = i;
			break;
		}
	}
	vector<int> ans;
	int prev = -1;
	while(true){
		ans.pb(pos);
		int ok = 0;
		for(auto x : adj[pos]){
			if(x != prev){
				prev = pos, pos = x, ok = 1;
				break;
			}
		}
		if(!ok) break;
	}
	// cout<<"ans : ";
	// for(auto x : ans) cout<<x<<" ";
	// cout<<"\n";
	Answer(ans);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 976 KB # of queries: 2847
2 Correct 31 ms 720 KB # of queries: 2838
3 Correct 31 ms 984 KB # of queries: 2972
4 Correct 36 ms 468 KB # of queries: 2965
5 Correct 32 ms 976 KB # of queries: 2980
6 Correct 38 ms 976 KB # of queries: 2989
7 Correct 36 ms 976 KB # of queries: 2961
8 Correct 36 ms 856 KB # of queries: 2831
9 Correct 37 ms 720 KB # of queries: 2973
10 Correct 19 ms 476 KB # of queries: 1729
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 2 ms 600 KB # of queries: 101
16 Correct 2 ms 460 KB # of queries: 237
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 976 KB # of queries: 2847
2 Correct 31 ms 720 KB # of queries: 2838
3 Correct 31 ms 984 KB # of queries: 2972
4 Correct 36 ms 468 KB # of queries: 2965
5 Correct 32 ms 976 KB # of queries: 2980
6 Correct 38 ms 976 KB # of queries: 2989
7 Correct 36 ms 976 KB # of queries: 2961
8 Correct 36 ms 856 KB # of queries: 2831
9 Correct 37 ms 720 KB # of queries: 2973
10 Correct 19 ms 476 KB # of queries: 1729
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 2 ms 600 KB # of queries: 101
16 Correct 2 ms 460 KB # of queries: 237
17 Correct 715 ms 1028 KB # of queries: 19415
18 Correct 720 ms 1240 KB # of queries: 19202
19 Correct 722 ms 804 KB # of queries: 19415
20 Correct 656 ms 1492 KB # of queries: 18195
21 Correct 592 ms 1036 KB # of queries: 17121
22 Correct 739 ms 1260 KB # of queries: 19444
23 Correct 731 ms 1008 KB # of queries: 19406
24 Correct 208 ms 728 KB # of queries: 8961
25 Correct 722 ms 1032 KB # of queries: 18991
26 Correct 646 ms 1048 KB # of queries: 17782
27 Correct 218 ms 732 KB # of queries: 8945
28 Correct 381 ms 1048 KB # of queries: 14912
29 Correct 373 ms 792 KB # of queries: 14894
30 Correct 368 ms 796 KB # of queries: 14912