Submission #1306665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306665		Tymond	도서관 (JOI18_library)	C++20	100 / 100	114 ms	448 KiB

library

#include "library.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

vi used;
int n;

int join(int x, bool justStarted){
	vi nused = {};
	for(int j = 1; j <= n; j++){
		if(!used[j]){
			nused.pb(j);
		}
	}

	int l = 0;
	int p = sz(nused);
	int mid;
	while(l < p){
		mid = (l + p) / 2;
		vi M(n, 0);
		for(int j = 0; j <= mid; j++){
			M[nused[j] - 1] = 1;
		}

		for(int j = 1; j <= n; j++){
			if(used[j]){
				M[j - 1] = 1;
			}
		}

		int r1 = Query(M);
		M[x - 1] = 0;
		int r2 = Query(M);
		if(justStarted){
			if(r2 < r1){
				l = mid + 1;
			}else{
				p = mid;
			}
		}else{
			if(r2 > r1){
				p = mid;
			}else{
				l = mid + 1;
			}
		}
	}
	return (l == sz(nused) ? n + 1 : nused[l]);
}

void Solve(int N){
	n = N;
	used.assign(n + 1, 0);

	vi p = {1};
	used[1] = 1;
	while(true){
		int x = join(p.back(), (sz(p) == 1));
		if(x == n + 1){
			break;
		}
		used[x] = 1;
		p.pb(x);
	}

	reverse(all(p));

	while(sz(p) < n){
		int x = join(p.back(), (sz(p) == 1));
		used[x] = 1;
		p.pb(x);
	}

	Answer(p);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81