Submission #1164589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164589		Sang	Library (JOI18_library)	C++20	100 / 100	151 ms	4396 KiB

library

#ifndef _Pbrngw_
#include "library.h"
#endif // _Pbrngw_
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n;
bool block[N];
deque<int> dq;

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

bool check(int x, int y, int i){
    FOR (j, 0, i){
        int c = (x>>j)&1;
        int c2 = (y>>j)&1;
        if (c == c2) continue;
        return 0;
    }
    return 1;
}

void findNxt(int u, bool frt){
    int x = 0;
    vector<int> M(n, 0);
    FOR (i, 0, 9){
        FOR (j, 0, n - 1) M[j] = 0;
        int ok = 0;
        FOR (j, 1, n){
            if (block[j]) continue;
            if (check(x, j, i)) M[j-1] = 1, ok = 1;
        }

        if (ok ==0){
            x += (1<<i);
        } else {
            int cur = Query(M);
            M[u-1] = 1;
            if (cur < Query(M)){
                x += (1<<i);
            }
        }
    }
    if (x > n) return;
    block[x] = 1;
    if (frt) dq.push_front(x);
    else dq.pb(x);
    findNxt(x, frt);
}

void Solve(int _n){
    n = _n;
    vector<int> M(n, 0), res(n, 0);
    if (n <= 2){
        FOR (i, 0, n - 1) res[i] = i + 1;
        Answer(res);
        return;
    }

    dq.pb(1);
    block[1] = 1;
    int x = 0;
    FOR (i, 0, 9){
        FOR (j, 0, n - 1) M[j] = 0;
        int ok = 0;
        FOR (j, 1, n){
            if (block[j]) continue;
            if (check(x, j, i)) M[j-1] = 1, ok = 1;
        }
        if (ok ==0){
            x += (1<<i);
        } else {
            int cur = Query(M);
            M[0] = 1;
            if (cur < Query(M)){
                x += (1<<i);
            }
        }
    }
    assert(x <= n);
    block[x] = 1;
    dq.push_front(x);
    findNxt(x, 1);
    findNxt(1, 0);
    FOR (i, 0, n - 1) res[i] = dq[i];
    Answer(res);
}

#ifdef _Pbrngw_

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);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    judge.init();
	Solve(judge.N);
	judge.end();

    return 0;
}

#endif // _Pbrngw_

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