제출 #58680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58680		TadijaSebez	도서관 (JOI18_library)	C++11	100 / 100	914 ms	700 KiB

library

#include "library.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <ctime>
using namespace std;
#define pb push_back
const int N=1050;
//-----------------------//
/*
bool _use[N];
int _N,_Q;
int _p[N];
vector<int> _P;
int Query(vector<int> a)
{
	_Q++;
	int i;
	for(i=1;i<=_N;i++) _use[i]=0;
	for(i=0;i<a.size();i++) _use[_p[a[i]]]=1;
	int sol=0;
	for(i=1;i<=_N;i++)
	{
		if(_use[i] && !_use[i-1]) sol++;
	}
	return sol;
}
bool ok=0;
void Answer(vector<int> a)
{
	//printf("Number of queries: %i\n",_Q);
	if(a==_P){ ok=1;printf("OK\n");return;}
	reverse(_P.begin(),_P.end());
	if(a==_P) ok=1;//printf("OK\n");
	else printf("WA\n"),ok=0;
}
*/
//-----------------------//
bool done[N];
deque<int> ans;
void Fill(vector<int> &a, int n)
{
	a.clear();
	for(int i=1;i<=n;i++) if(!done[i]) a.pb(i);
}
bool was[N];
int MyQuery(vector<int> a, int n)
{
	int i;
	for(i=1;i<=n;i++) was[i]=0;
	for(i=0;i<a.size();i++) was[a[i]]=1;
	vector<int> ask;
	for(i=1;i<=n;i++) ask.pb(was[i]);
	return Query(ask);
}
bool Ask(vector<int> a, int i, int n)
{
	int sol1=MyQuery(a,n);
	a.pb(i);
	int sol2=MyQuery(a,n);
	return sol1>=sol2;
}
void Solve(int n)
{
	int i;
	for(i=1;i<=n;i++) done[i]=0;
	ans.push_back(1);
	done[1]=1;
	vector<int> my,tmp[2];
	while(ans.size()<n)
	{
		int x=ans.back();
		//printf("1: %i\n",x);
		Fill(my,n);
		if(!Ask(my,x,n)) break;
		while(my.size()>1)
		{
			tmp[0].clear();tmp[1].clear();
			for(i=0;i<my.size();i++) tmp[i&1].pb(my[i]);
			if(Ask(tmp[0],x,n)) my=tmp[0];
			else my=tmp[1];
		}
		ans.push_back(my[0]);
		done[my[0]]=1;
	}
	while(ans.size()<n)
	{
		int x=ans.front();
		//printf("2: %i\n",x);
		Fill(my,n);
		while(my.size()>1)
		{
			tmp[0].clear();tmp[1].clear();
			for(i=0;i<my.size();i++) tmp[i&1].pb(my[i]);
			if(Ask(tmp[0],x,n)) my=tmp[0];
			else my=tmp[1];
		}
		ans.push_front(my[0]);
		done[my[0]]=1;
	}
	vector<int> ret;
	while(ans.size()) ret.pb(ans.front()),ans.pop_front();
	Answer(ret);
}
//-----------------------//
/*
void StressTest()
{
	srand(time(0));
	int t,c=0,i,j;
	scanf("%i",&t);
	for(j=1;j<=t;j++)
	{
		_N=rand()%50+1;
		//printf("%i\n",_N);
		_P.clear();
		for(i=0;i<_N;i++) _P.pb(i+1);
		random_shuffle(_P.begin(),_P.end());
		for(i=0;i<_N;i++) _p[_P[i]]=i+1;//printf("%i ",_P[i]);
		//printf("\n");
		Solve(_N);
		if(!ok)
		{
			printf("%i\n",_N);
			for(i=0;i<_N;i++) printf("%i ",_P[i]);
			printf("\n");
		}
		else c++;
	}
	printf("%i of %i is correct!\n",c,t);
}
int main()
{
	StressTest();return 0;
	scanf("%i",&_N);
	int i,x;
	for(i=0;i<_N;i++) scanf("%i",&x),_P.pb(x),_p[x]=i+1;
	Solve(_N);
	return 0;
}
*/
//-----------------------//

컴파일 시 표준 에러 (stderr) 메시지

library.cpp: In function 'int MyQuery(std::vector<int>, int)':
library.cpp:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<a.size();i++) was[a[i]]=1;
          ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size()<n)
        ~~~~~~~~~~^~
library.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<my.size();i++) tmp[i&1].pb(my[i]);
            ~^~~~~~~~~~
library.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size()<n)
        ~~~~~~~~~~^~
library.cpp:96:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<my.size();i++) tmp[i&1].pb(my[i]);
            ~^~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81