oj.uz

답안 #260847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260847 2020-08-11T05:47:25 Z arnold518 도서관 (JOI18_library) C++14
100 / 100
 512 ms 504 KB 
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

int N, bef;
vector<int> todo, T, ans;

int solve(int l, int r)
{
	if(l==r) return todo[l];

	int p, q;
	int mid=l+r>>1;
	for(int i=l; i<=mid; i++) T[todo[i]-1]=1;
	p=Query(T);
	T[bef-1]=1;
	q=Query(T);
	T[bef-1]=0;
	for(int i=l; i<=mid; i++) T[todo[i]-1]=0;

	if(p==q) return solve(l, mid);
	else return solve(mid+1, r);
}

void Solve(int _N)
{
	N=_N;

	for(int i=1; i<=N; i++) todo.push_back(i);
	ans=vector<int>(N);

	T=vector<int>(N, 1);
	int now=0;
	for(int j=0; j+1<todo.size(); j++)
	{
		int p=todo[j];
		T[p-1]=0;
		int q=Query(T);
		if(q==1) { now=p; break; }
		T[p-1]=1;
	}
	if(now==0) now=todo.back();
	for(int j=0; j<todo.size(); j++) if(todo[j]==now)
	{
		todo.erase(todo.begin()+j);
		break;
	}
	ans[0]=now;

	for(int i=2; i<=N; i++)
	{
		T=vector<int>(N);
		bef=ans[i-2];
		int now=solve(0, todo.size()-1);
		for(int j=0; j<todo.size(); j++) if(todo[j]==now)
		{
			todo.erase(todo.begin()+j);
			break;
		}
		ans[i-1]=now;
	}

	Answer(ans);
}

Compilation message

library.cpp: In function 'int solve(int, int)':
library.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
library.cpp: In function 'void Solve(int)':
library.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0; j+1<todo.size(); j++)
               ~~~^~~~~~~~~~~~
library.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0; j<todo.size(); j++) if(todo[j]==now)
               ~^~~~~~~~~~~~
library.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<todo.size(); j++) if(todo[j]==now)
                ~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 256 KB # of queries: 2387
2 Correct 55 ms 256 KB # of queries: 2433
3 Correct 43 ms 256 KB # of queries: 2638
4 Correct 36 ms 256 KB # of queries: 2593
5 Correct 46 ms 256 KB # of queries: 2504
6 Correct 37 ms 256 KB # of queries: 2553
7 Correct 31 ms 256 KB # of queries: 2568
8 Correct 27 ms 256 KB # of queries: 2402
9 Correct 29 ms 256 KB # of queries: 2512
10 Correct 27 ms 256 KB # of queries: 1478
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 1 ms 384 KB # of queries: 4
14 Correct 1 ms 256 KB # of queries: 7
15 Correct 1 ms 256 KB # of queries: 73
16 Correct 2 ms 384 KB # of queries: 187

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 256 KB # of queries: 2387
2 Correct 55 ms 256 KB # of queries: 2433
3 Correct 43 ms 256 KB # of queries: 2638
4 Correct 36 ms 256 KB # of queries: 2593
5 Correct 46 ms 256 KB # of queries: 2504
6 Correct 37 ms 256 KB # of queries: 2553
7 Correct 31 ms 256 KB # of queries: 2568
8 Correct 27 ms 256 KB # of queries: 2402
9 Correct 29 ms 256 KB # of queries: 2512
10 Correct 27 ms 256 KB # of queries: 1478
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 1 ms 384 KB # of queries: 4
14 Correct 1 ms 256 KB # of queries: 7
15 Correct 1 ms 256 KB # of queries: 73
16 Correct 2 ms 384 KB # of queries: 187
17 Correct 466 ms 384 KB # of queries: 18008
18 Correct 434 ms 504 KB # of queries: 17231
19 Correct 436 ms 384 KB # of queries: 17451
20 Correct 388 ms 384 KB # of queries: 16277
21 Correct 346 ms 384 KB # of queries: 15362
22 Correct 407 ms 376 KB # of queries: 17617
23 Correct 430 ms 384 KB # of queries: 17170
24 Correct 155 ms 384 KB # of queries: 7885
25 Correct 441 ms 384 KB # of queries: 17118
26 Correct 406 ms 384 KB # of queries: 15989
27 Correct 170 ms 256 KB # of queries: 7994
28 Correct 512 ms 384 KB # of queries: 17935
29 Correct 444 ms 384 KB # of queries: 17915
30 Correct 466 ms 384 KB # of queries: 17935