답안 #639423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639423 2022-09-09T23:35:40 Z beaconmc 도서관 (JOI18_library) C++14
100 / 100
472 ms 508 KB
#include <bits/stdc++.h>
typedef int ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


#include "library.h"
using namespace std;

ll b = 0;
ll n = 1;
unordered_set<ll> sussies;

int q(vector<int> arr){
	if (arr.size()==0) return 0;
	vector<ll> query(n);
	for (auto&i : arr){
		query[i] = 1;
	}
	return Query(query);
}

bool begins(vector<int> oldarr){
	vector<int> arr;
	for (auto&i : oldarr){
		if (!sussies.count(i)) arr.push_back(i);
	}

	int result = q(arr);
	arr.push_back(b);
	int result2 = q(arr);
	if (result == result2) return 1;
	return 0;
}


void Solve(int N)
{
	n = N;

	FOR(i,0,n){
		vector<ll> queries;
		FOR(j,0,n){
			if (j!=i) queries.push_back(j);
		}
		if (q(queries)==1){
			b = i;
			break;
		}
	}
	vector<ll> ans;
	ans.push_back(b);
	sussies.insert(b);


	FOR(i,0,n-1){
		vector<int> stuff;

		FOR(j,0,n){
			if (!sussies.count(j)) stuff.push_back(j);
		}
		ll l=0;
		ll r = stuff.size();

		while (l<r){
			vector<ll> queries;
			ll mid = (l+r)/2;
			FOR(i,l,mid+1){
				queries.push_back(stuff[i]);
			}

			bool sus = begins(queries);


			if (sus) r = mid;
			else l = mid+1;
		}
		b = stuff[l];
		sussies.insert(b);
		ans.push_back(b);

	};

	FOR(i,0,n){
		ans[i] += 1;
	}

	Answer(ans);

}
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 308 KB # of queries: 2411
2 Correct 36 ms 208 KB # of queries: 2455
3 Correct 40 ms 428 KB # of queries: 2664
4 Correct 34 ms 300 KB # of queries: 2613
5 Correct 38 ms 308 KB # of queries: 2534
6 Correct 34 ms 312 KB # of queries: 2567
7 Correct 44 ms 304 KB # of queries: 2580
8 Correct 32 ms 300 KB # of queries: 2416
9 Correct 38 ms 308 KB # of queries: 2552
10 Correct 24 ms 292 KB # of queries: 1494
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 8
14 Correct 0 ms 208 KB # of queries: 11
15 Correct 2 ms 208 KB # of queries: 85
16 Correct 3 ms 208 KB # of queries: 195
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 308 KB # of queries: 2411
2 Correct 36 ms 208 KB # of queries: 2455
3 Correct 40 ms 428 KB # of queries: 2664
4 Correct 34 ms 300 KB # of queries: 2613
5 Correct 38 ms 308 KB # of queries: 2534
6 Correct 34 ms 312 KB # of queries: 2567
7 Correct 44 ms 304 KB # of queries: 2580
8 Correct 32 ms 300 KB # of queries: 2416
9 Correct 38 ms 308 KB # of queries: 2552
10 Correct 24 ms 292 KB # of queries: 1494
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 8
14 Correct 0 ms 208 KB # of queries: 11
15 Correct 2 ms 208 KB # of queries: 85
16 Correct 3 ms 208 KB # of queries: 195
17 Correct 472 ms 440 KB # of queries: 18050
18 Correct 420 ms 392 KB # of queries: 17249
19 Correct 446 ms 436 KB # of queries: 17493
20 Correct 427 ms 392 KB # of queries: 16333
21 Correct 365 ms 508 KB # of queries: 15390
22 Correct 415 ms 396 KB # of queries: 17681
23 Correct 394 ms 496 KB # of queries: 17244
24 Correct 154 ms 428 KB # of queries: 7909
25 Correct 402 ms 460 KB # of queries: 17150
26 Correct 384 ms 476 KB # of queries: 16033
27 Correct 126 ms 460 KB # of queries: 8020
28 Correct 457 ms 316 KB # of queries: 17955
29 Correct 419 ms 504 KB # of queries: 17935
30 Correct 430 ms 456 KB # of queries: 17955