oj.uz

Submission #992707

# Submission time Handle Problem Language Result Execution time Memory
992707 2024-06-05T04:57:39 Z kokoxuya Library (JOI18_library) C++14
100 / 100
 346 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;
		//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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 344 KB # of queries: 2672
2 Correct 18 ms 416 KB # of queries: 2628
3 Correct 20 ms 344 KB # of queries: 2776
4 Correct 30 ms 592 KB # of queries: 2760
5 Correct 18 ms 344 KB # of queries: 2766
6 Correct 20 ms 344 KB # of queries: 2780
7 Correct 26 ms 344 KB # of queries: 2728
8 Correct 26 ms 596 KB # of queries: 2678
9 Correct 33 ms 420 KB # of queries: 2814
10 Correct 15 ms 420 KB # of queries: 1648
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 1 ms 344 KB # of queries: 8
15 Correct 1 ms 344 KB # of queries: 92
16 Correct 3 ms 344 KB # of queries: 224

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 344 KB # of queries: 2672
2 Correct 18 ms 416 KB # of queries: 2628
3 Correct 20 ms 344 KB # of queries: 2776
4 Correct 30 ms 592 KB # of queries: 2760
5 Correct 18 ms 344 KB # of queries: 2766
6 Correct 20 ms 344 KB # of queries: 2780
7 Correct 26 ms 344 KB # of queries: 2728
8 Correct 26 ms 596 KB # of queries: 2678
9 Correct 33 ms 420 KB # of queries: 2814
10 Correct 15 ms 420 KB # of queries: 1648
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 1 ms 344 KB # of queries: 8
15 Correct 1 ms 344 KB # of queries: 92
16 Correct 3 ms 344 KB # of queries: 224
17 Correct 328 ms 420 KB # of queries: 18720
18 Correct 324 ms 436 KB # of queries: 18382
19 Correct 346 ms 428 KB # of queries: 18674
20 Correct 302 ms 596 KB # of queries: 17412
21 Correct 273 ms 424 KB # of queries: 16246
22 Correct 333 ms 440 KB # of queries: 18628
23 Correct 324 ms 592 KB # of queries: 18656
24 Correct 106 ms 424 KB # of queries: 8566
25 Correct 321 ms 424 KB # of queries: 18172
26 Correct 286 ms 420 KB # of queries: 16866
27 Correct 111 ms 344 KB # of queries: 8556
28 Correct 167 ms 420 KB # of queries: 9858
29 Correct 160 ms 424 KB # of queries: 9846
30 Correct 176 ms 428 KB # of queries: 9858