제출 #288674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288674		Fasho	동굴 (IOI13_cave)	C++14	100 / 100	1245 ms	1148 KiB

cave

#include <bits/stdc++.h>
#define NN 100005
#define ll long long int
#define fo(i,x,y)   for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
// #define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define mod 1000000007
#include "cave.h"
using namespace std;
 
int n,m,ar[NN],sum,t,tutmac[NN],tut[NN],flag,ans[NN];
 
bool check(int l,int r,int x)
{
	fo(i,0,n-1)
	tutmac[i]=!flag;
	// fo(i,0,n-1)
	// cout<<tutmac[i]<<sp;
	// cout<<endl;
	fo(i,l,r)
		tutmac[i]=flag;
	fo(i,0,n-1)
		if(tut[i]!=-1)
			tutmac[i]=tut[i];
	int y=tryCombination(tutmac);
	// cout<<"[d]"<<sp<<x<<sp<<l<<sp<<r<<endl;
	// y<<endl;
	// cout<<y<<endl<<endl;
 
	if(y>x || y==-1)
		return 1;
	return 0;
}
 
void bs(int x)
{
	int l=0,r=n-1;
	 flag=1;
	fo(i,0,n-1)
		tutmac[i]=0;
	fo(i,0,n-1)
		if(tut[i]!=-1)
			tutmac[i]=tut[i];
	int y=tryCombination(tutmac);
	if(y>x || y==-1)
		flag=0;
	// cout<<"[d2]"<<sp;
	// cout<<x<<sp<<flag<<endl;
	while(l<r)
	{
		if(l==r-1)
		{
			if(check(r,r,x))
				l=r;
			break;
		}
		int mid=(l+r)/2;
		if(check(l,mid,x))
			r=mid;
		else
			l=mid+1;
	}
	tut[l]=flag;
	ans[l]=x;
 
 
}
 
void exploreCave(int N) {
    n=N;
	memset(tut,-1,sizeof(tut));
    fo(i,0,n-1)
		bs(i);
	// fo(i,0,n-1)
		// cout<<tut[i]<<sp;
	// fo(i,0,n-1)
		// cout<<ans[i]<<sp;
 
    answer(tut,ans);	
}

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