Submission #1129018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129018		crafticat	Library (JOI18_library)	C++17	0 / 100	20 ms	416 KiB

library

#include <bits/stdc++.h>

#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
#define s second
#define F0R(i,n) for(int i = 0; i < n;i++)
#define FOR(i,j,n) for(int i = j; i < n;i++)
using ll = long long;
using vi = V<int>;

int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);
int n;
vi vis;

int test(int l, int r, int expel = -1) {
    vi arr = vis;
    FOR(i,l,r)
        arr[i] = 1;

    if (expel != -1) arr[expel] = 0;
    if (arr == vis) return -1; // No changes were made
    F0R(i, n)
        arr[i] = !arr[i];
    return Query(arr);
}

int getNext(int l, int r, int x) {
    if (r - l <= 1)
        return l;

    int mid = (l + r) / 2;
    // without
    vis[x] = 0;
    int without = test(l, mid, x);
    vis[x] = 1;
    int with = test(l, mid);

    if (without > with && with != -1)
        return getNext(l, mid, x);
    else
        return getNext(mid, r, x);
}

void Solve(int N)
{
    if (N == 1) {
        Answer({1});
        return;
    }

    n = N;
    vi edges;
    vi ans;
    vis.resize(N);

    F0R(i, N) {
        if (i == 685) {
            int stop = 25;
        }
        if (test(i, i + 1) == 1)
            edges.push_back(i);
    }

    if (edges.empty()) exit(5);
    int last = edges[0];
    ans.push_back(last + 1);
    F0R(i, N - 2) {
        int next = getNext(0, n, last);
        last = next;
        ans.push_back(next + 1);
    }

    ans.push_back(edges[1] + 1);
    Answer(ans);
}


#if DEBUG
using namespace std;
void Solve(int N);
int myrandom (int i) { return std::rand()%i;}

namespace {
struct Judge
{
	int N;
	int A[1002];
	int pos[1002];
	bool f[1002];
	int query_c;
	bool answered;
	void init()
	{
		query_c=0;
		N = 1000;
		answered=false;

        F0R(i, N)
            pos[i + 1] = i;
        int stop = 25;
    }
	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 && f[i])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);
}

int main()
{
	judge.init();
	Solve(judge.N);
	judge.end();
}
#endif

//5
//4
//2
//5
//3
//1

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