제출 #992707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992707		kokoxuya	도서관 (JOI18_library)	C++14	100 / 100	346 ms	596 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"


#include <bits/stdc++.h>
//using namespace std;
//#define int long long
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first
#define debu(x) (cerr << #x  << " = "<< x << "\n")
#define defN 1001
#define mp make_pair


using namespace std;
int n;
vector<int>visited(defN,0);
vector<int>adjto(defN);
vector<bool>alrhave(defN,0);
int t1;

pair<int,vector<int>>dfs(int currnode, int counter, vector<int> &curr)
{
	counter++;//cout<<currnode << " : ";
	//sssdebu(counter);
	curr.pb(currnode);
	visited[currnode] = true;
	if (!visited[adjto[currnode]] && adjto[currnode] != 0)
	{
		auto xx = dfs(adjto[currnode],counter,curr);
		return xx;
	}
	else
	{
		pair<int,vector<int>> xx = {counter,curr};
		return xx;
	}
}

//here its 0-indexed
bool checkers(int lo, int mid, int x)
{
	//cout << lo << " " << mid << "\n";
	vector<int>M(n,0);
	int c = 0;
	for (int a = lo; a <= mid; a++)
	{
		if (a == x || alrhave[a])continue;
		M[a] = 1;
		c++;
	}
	//cout << "see : "<< c << "\n";
	if (c == 0)
	{
		//cout << 0 <<"\n";
		return false;}
	int y = Query(M);
	
	M[x] = 1;
	int z = Query(M);
	
	//cout << (z <= y) <<"\n";
	return (z <= y);
}

void Solve(int N)
{
	n = N;

	t1 = -1;
	int next = 1;
	alrhave[0] = true;
	for (int a = 1; a < N; a++)
	{
		int ans = -1;
		//if (next!=1)
			//cout << "for book number : " << next << "\n";
		int hi = N, lo = 1,mid;
		while (lo <= hi)
		{
			mid = (hi + lo)/2;
			//cout << "krakatoa "<< lo << " " << mid << "\n";
			if (checkers(lo-1,mid-1,next-1))
			{
				hi = mid - 1;
				ans = mid;
			}
			else
			{
				lo = mid + 1;
			}
		}
		if (ans == -1)
		{
			//cout << "literally how";
			next = 1;
			t1 = adjto[1];
			a-=1;
			continue;
		}
		adjto[next] = ans;
		alrhave[ans-1] = true;
		next = ans;
		//cout << ans << "\n";
	}


	//cout << "outputting adjto:\n";
	////cout << t1<<" ";
	//for (int y = 1; y <= n; y++)
	//{cout << adjto[y] << " ";}
	vector<int> res;
	////cout << "start mint chocolate:\n";
	
	/*for (int a = 1; a <= N; a++)
	{
		vector<int>kk;
		pair<int,vector<int>> j = dfs(a,0,kk);
		cout << j.ff << " ";
		if (j.ff == N)
		{
			cout << "this happened\n";
			res = j.ss;
			break;
		}
	}*/
	vector<int>kk;
	pair<int,vector<int>> j = dfs(1,0,kk);
	res = j.ss;
	if (t1 != -1)
	{
		vector<int>kk;
		pair<int,vector<int>> k = dfs(t1,0,kk);
		reverse(k.ss.begin(),k.ss.end());
		res.insert(res.begin(), k.ss.begin(),k.ss.end());
	}
	//cout << "\nwhy no more mint chocolate end\n";

	/*cout << "outputting res:\n";
	for (int x : res)
	{
		cout << x << " ";
	}*/
	Answer(res);
}

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