oj.uz

답안 #992703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
992703 2024-06-05T04:34:22 Z kokoxuya 도서관 (JOI18_library) C++14
0 / 100
 209 ms 596 KB 
#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;
		//cout << "for book number : " << next << "\n";
		int hi = N, lo = 1,mid;
		while (lo <= hi)
		{
			mid = (hi + lo)/2;
			if (checkers(lo-1,mid-1,next-1))
			{
				hi = mid - 1;
				ans = mid;
			}
			else
			{
				lo = mid + 1;
			}
		}
		if (ans == -1)
		{
			next = 1;
			t1 = adjto[1];
			a-=1;
			continue;
		}
		adjto[next] = ans;
		alrhave[ans-1] = true;
		next = ans;
		//c/out << 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
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 596 KB # of queries: 2672
2 Correct 25 ms 420 KB # of queries: 2628
3 Correct 28 ms 420 KB # of queries: 2776
4 Correct 39 ms 344 KB # of queries: 2760
5 Correct 22 ms 344 KB # of queries: 2766
6 Correct 26 ms 344 KB # of queries: 2780
7 Correct 28 ms 420 KB # of queries: 2728
8 Correct 29 ms 344 KB # of queries: 2678
9 Correct 40 ms 420 KB # of queries: 2814
10 Runtime error 209 ms 420 KB Execution killed with signal 13
11 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 596 KB # of queries: 2672
2 Correct 25 ms 420 KB # of queries: 2628
3 Correct 28 ms 420 KB # of queries: 2776
4 Correct 39 ms 344 KB # of queries: 2760
5 Correct 22 ms 344 KB # of queries: 2766
6 Correct 26 ms 344 KB # of queries: 2780
7 Correct 28 ms 420 KB # of queries: 2728
8 Correct 29 ms 344 KB # of queries: 2678
9 Correct 40 ms 420 KB # of queries: 2814
10 Runtime error 209 ms 420 KB Execution killed with signal 13
11 Halted 0 ms 0 KB -