oj.uz

답안 #827838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827838 2023-08-16T20:01:57 Z MohamedAhmed04 도서관 (JOI18_library) C++14
100 / 100
 217 ms 592 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

const int MAX = 1000 + 10 ;

int n ;

vector<int>v[MAX] ;
int taken[MAX] ;

bool check(int l , int r)
{
	vector<int>vq(n , 0) ;
	int cnt = r-l+1 ;
	for(int i = l ; i <= r ; ++i)
	{
		vq[i] = 1 ;
		for(auto &j : v[i])
			cnt -= (j > i && j <= r) ;
	}
	return (Query(vq) < cnt) ;
}

void Find_Adjacent(int idx , int cnt)
{
	for(int i = 0 ; i < cnt ; ++i)
	{
		int l = 0 , r = idx ;
		int idx2 = -1 ; 
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(check(mid , idx))
				idx2 = mid , l = mid+1 ;
			else
				r = mid-1 ;
		}
		v[idx].push_back(idx2) , v[idx2].push_back(idx) ;
	}
}

void Solve(int N)
{
	n = N ;
	if(n == 1)
	{
		Answer({1}) ;
		return ;
	}
	vector<int>vq(n , 0) ;
	int cur = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		++cur ;
		vq[i] = 1 ;
		int x = Query(vq) ;
		Find_Adjacent(i , cur - x) ;
		cur = x ;
	}
	vector<int>ans ;
	int x = -1 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(v[i].size() == 1)
		{
			x = i ;
			break ;
		}
	}
	while(ans.size() < n)
	{
		ans.push_back(x+1) ;
		taken[x] = 1 ;
		for(auto &i : v[x])
		{
			if(!taken[i])
			{
				x = i ;
				break ;
			}
		}
	}
	Answer(ans) ;
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  while(ans.size() < n)
      |        ~~~~~~~~~~~^~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 208 KB # of queries: 1525
2 Correct 18 ms 208 KB # of queries: 1522
3 Correct 21 ms 332 KB # of queries: 1599
4 Correct 17 ms 324 KB # of queries: 1587
5 Correct 13 ms 320 KB # of queries: 1597
6 Correct 16 ms 208 KB # of queries: 1587
7 Correct 22 ms 332 KB # of queries: 1591
8 Correct 18 ms 324 KB # of queries: 1522
9 Correct 21 ms 316 KB # of queries: 1597
10 Correct 9 ms 336 KB # of queries: 953
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 4
13 Correct 0 ms 208 KB # of queries: 7
14 Correct 0 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 65
16 Correct 2 ms 208 KB # of queries: 140

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 208 KB # of queries: 1525
2 Correct 18 ms 208 KB # of queries: 1522
3 Correct 21 ms 332 KB # of queries: 1599
4 Correct 17 ms 324 KB # of queries: 1587
5 Correct 13 ms 320 KB # of queries: 1597
6 Correct 16 ms 208 KB # of queries: 1587
7 Correct 22 ms 332 KB # of queries: 1591
8 Correct 18 ms 324 KB # of queries: 1522
9 Correct 21 ms 316 KB # of queries: 1597
10 Correct 9 ms 336 KB # of queries: 953
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 4
13 Correct 0 ms 208 KB # of queries: 7
14 Correct 0 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 65
16 Correct 2 ms 208 KB # of queries: 140
17 Correct 217 ms 340 KB # of queries: 10311
18 Correct 175 ms 336 KB # of queries: 10185
19 Correct 180 ms 320 KB # of queries: 10270
20 Correct 174 ms 456 KB # of queries: 9626
21 Correct 153 ms 336 KB # of queries: 9047
22 Correct 199 ms 332 KB # of queries: 10291
23 Correct 191 ms 448 KB # of queries: 10279
24 Correct 68 ms 324 KB # of queries: 4778
25 Correct 172 ms 592 KB # of queries: 10050
26 Correct 168 ms 336 KB # of queries: 9399
27 Correct 63 ms 336 KB # of queries: 4762
28 Correct 173 ms 348 KB # of queries: 9986
29 Correct 168 ms 448 KB # of queries: 9975
30 Correct 187 ms 348 KB # of queries: 9986