oj.uz

Submission #44941

# Submission time Handle Problem Language Result Execution time Memory
44941 2018-04-09T18:22:01 Z Alexa2001 Library (JOI18_library) C++17
100 / 100
 678 ms 720 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 248 KB Output is correct
2 Correct 71 ms 308 KB Output is correct
3 Correct 56 ms 512 KB Output is correct
4 Correct 49 ms 512 KB Output is correct
5 Correct 56 ms 512 KB Output is correct
6 Correct 66 ms 516 KB Output is correct
7 Correct 49 ms 516 KB Output is correct
8 Correct 43 ms 516 KB Output is correct
9 Correct 49 ms 540 KB Output is correct
10 Correct 24 ms 580 KB Output is correct
11 Correct 1 ms 580 KB Output is correct
12 Correct 2 ms 580 KB Output is correct
13 Correct 2 ms 580 KB Output is correct
14 Correct 2 ms 580 KB Output is correct
15 Correct 3 ms 580 KB Output is correct
16 Correct 4 ms 580 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 248 KB Output is correct
2 Correct 71 ms 308 KB Output is correct
3 Correct 56 ms 512 KB Output is correct
4 Correct 49 ms 512 KB Output is correct
5 Correct 56 ms 512 KB Output is correct
6 Correct 66 ms 516 KB Output is correct
7 Correct 49 ms 516 KB Output is correct
8 Correct 43 ms 516 KB Output is correct
9 Correct 49 ms 540 KB Output is correct
10 Correct 24 ms 580 KB Output is correct
11 Correct 1 ms 580 KB Output is correct
12 Correct 2 ms 580 KB Output is correct
13 Correct 2 ms 580 KB Output is correct
14 Correct 2 ms 580 KB Output is correct
15 Correct 3 ms 580 KB Output is correct
16 Correct 4 ms 580 KB Output is correct
17 Correct 592 ms 716 KB Output is correct
18 Correct 609 ms 716 KB Output is correct
19 Correct 678 ms 716 KB Output is correct
20 Correct 508 ms 716 KB Output is correct
21 Correct 527 ms 716 KB Output is correct
22 Correct 589 ms 716 KB Output is correct
23 Correct 581 ms 716 KB Output is correct
24 Correct 192 ms 716 KB Output is correct
25 Correct 587 ms 716 KB Output is correct
26 Correct 503 ms 720 KB Output is correct
27 Correct 177 ms 720 KB Output is correct
28 Correct 504 ms 720 KB Output is correct
29 Correct 466 ms 720 KB Output is correct
30 Correct 518 ms 720 KB Output is correct