제출 #870852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870852		HuyQuang_re_Zero	동굴 (IOI13_cave)	C++14	100 / 100	499 ms	812 KiB

cave

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "cave.h"
using namespace std;
int n,a[5002],b[5002],door[5002],i,j;
/*
struct Interactive
{
    int n=4,True[4]={ 1,1,1,0 },Door[4]={ 3,1,0,2 },d[5002];
    int Try(int a[])
    {
        for(int i=0;i<n;i++)
            if(a[i]==True[i]) d[Door[i]]=0; else d[Door[i]]=1;
        for(int i=0;i<n;i++)
            if(d[i]==1) return i;
        return -1;
    }
} IR;

int tryCombination(int a[])
{
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<'\n';
    return IR.Try(a);
}
void answer(int a[],int b[])
{
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<'\n';
    for(int i=0;i<n;i++) cout<<b[i]<<" ";
}*/

int check_close(int u,int cnt,int ch)
{
    for(int i=0;i<n;i++)
        if(a[i+1]>-1) b[i]=a[i+1];
        else if(cnt>0)
        {
            cnt--;
            b[i]=ch;
        }
        else b[i]=0;
    return tryCombination(b)+1==u;
}
void Work()
{
    memset(a,-1,sizeof(a));
    for(i=1;i<=n;i++)
    {
        int k=check_close(i,n-i+1,0),l=1,r=n-i+1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check_close(i,mid,1)!=k) r=mid; else l=mid+1;
        }
        for(j=1;j<=n;j++)
            if(a[j]==-1)
            {
                l--;
                if(l==0) break;
            }
        a[j]=k;
        door[j-1]=i-1;
    }
    for(i=0;i<n;i++) b[i]=a[i+1];
    answer(b,door);
}
void exploreCave(int _n)
{
    n=_n;
    Work();
}
/*
int main()
{
    freopen("cave.inp","r",stdin);
    freopen("cave.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    exploreCave(n);
}
*/

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24