Submission #44941

#	Time	Username	Problem	Language	Result	Execution time	Memory
44941		Alexa2001	Library (JOI18_library)	C++17	100 / 100	678 ms	720 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

/*
namespace {
struct Judge
{
	int N;
	int A[1002];
	int pos[1002];
	bool f[1002];
	int query_c;
	bool answered;
	void init()
	{
		query_c=0;
		int ret=scanf("%d",&N); ret++;
		answered=false;
		for(int i=0;i<N;i++)ret=scanf("%d",&A[i]),pos[A[i]]=i;
	}
	int query(const vector<int>& M)
	{
		if(query_c==20000)
		{
			puts("Wrong Answer [3]");
			exit(0);
		}
		if(int(M.size())!=N)
		{
			puts("Wrong Answer [1]");
			exit(0);
		}
		bool all_zero=true;
		for(int i=0;i<N;i++)
		{
			if(M[i]!=0&&M[i]!=1)
			{
				puts("Wrong Answer [2]");
				exit(0);
			}
			if(M[i]==1)all_zero=false;
		}
		if(all_zero)
		{
			puts("Wrong Answer [2]");
			exit(0);
		}
		memset(f,0,sizeof(f));
		for(int i=0;i<N;i++)if(M[i])f[pos[i+1]]=true;
		bool las=false;
		int r=0;
		for(int i=0;i<N;i++)
		{
			if(las==false&&f[i]==true)r++;
			las=f[i];
		}
		query_c++;
		return r;
	}
	void answer(const vector<int>& res)
	{
		bool f1=true,f2=true;
		if(int(res.size())!=N)
		{
			puts("Wrong Answer [4]");
			exit(0);
		}
		if(answered)
		{
			puts("Wrong Answer [7]");
			exit(0);
		}
		answered=true;
		memset(f,0,sizeof(f));
		for(int i=0;i<N;i++)
		{
			if(res[i]<=0||res[i]>N)
			{
				puts("Wrong Answer [5]");
				exit(0);
			}
			if(f[res[i]])
			{
				puts("Wrong Answer [6]");
				exit(0);
			}
			f[res[i]]=true;
		}
		for(int i=0;i<N;i++)
		{
			f1&=A[i]==res[i];
			f2&=A[i]==res[N-i-1];
		}
		if(!f1&&!f2)
		{
			puts("Wrong Answer　[8]");
			exit(0);
		}
	}
	void end()
	{
		if(!answered)puts("Wrong Answer [7]");
		else printf("Accepted : %d\n",query_c);
	}
}judge;
}

int Query(const vector<int>& M)
{
	return judge.query(M);
}
void Answer(const vector<int>& res)
{
	judge.answer(res);
}
*/

bitset<1005> S;

int query(int pos, int n, int start)
{
    vector<int> v;
    int i; bool ok = 0;
    for(i=1; i<=pos; ++i) v.push_back(S[i]);
    for(; i<=n; ++i) v.push_back(0);
    if(start > 0) v[start-1] = 1;
        else if(start < 0) v[-start-1] = 0;
    for(i=0; i<n; ++i) if(v[i]) ok = 1;
    if(!ok) return 0;
    return Query(v);
}

void Solve(int n)
{
    int i, start = 0, st, dr, mid;
    vector<int> answer, vall;

    if(n == 1)
    {
        answer.push_back(1);
        Answer(answer);
        return;
    }

    for(i=1; i<=n; ++i) S[i] = 1, vall.push_back(i);

    for(i=1; i<=n && !start; ++i)
    {
        S[i] = 0;
        if(query(n, n, 0) == 1) start = i;
        S[i] = 1;
    }

    while(S.count() > 1)
    {
        vall.erase(find(vall.begin(), vall.end(), start));
        st = 0, dr = vall.size() - 1;
        while(st <= dr)
        {
            mid = (st+dr)/2;
            if(query(vall[mid], n, start) != query(vall[mid], n, -start)) st = mid + 1;
                else dr = mid - 1;
        }

        S[start] = 0;
        answer.push_back(start);
        start = vall[st];
    }

    answer.push_back(start);
    Answer(answer);
}
/*
int main()
{
	judge.init();
	Solve(judge.N);
	judge.end();
}
*/

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