Submission #260847

#	Time	Username	Problem	Language	Result	Execution time	Memory
260847		arnold518	Library (JOI18_library)	C++14	100 / 100	512 ms	504 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81