제출 #1129056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129056		crafticat	도서관 (JOI18_library)	C++20	100 / 100	202 ms	424 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];

    bool allZ = true;
    F0R(i,n) {
        if (arr[i]) allZ = false;
    }
    if (allZ) return 0;
    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 && without != -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 (test(i, i + 1) == 1)
            edges.push_back(i);
    }

    if (edges.size() < 2) 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;
        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(5);
		}
		if(int(M.size())!=N)
		{
			puts("Wrong Answer [1]");
			exit(5);
		}
		bool all_zero=true;
		for(int i=0;i<N;i++)
		{
			if(M[i]!=0&&M[i]!=1)
			{
				puts("Wrong Answer [2]");
				exit(5);
			}
			if(M[i]==1)all_zero=false;
		}
		if(all_zero)
		{
			puts("Wrong Answer [2]");
			exit(5);
		}
		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(5);

        }
		if(answered)
		{
			puts("Wrong Answer [7]");
            exit(5);

        }
		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(5);
                exit(5);

            }
			if(f[res[i]])
			{
				puts("Wrong Answer [6]");
				exit(5);
                exit(5);

            }
			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(5);
		}
	}
	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: 19 / 19
• Subtask 2: 81 / 81