Submission #234125

#	Time	Username	Problem	Language	Result	Execution time	Memory
234125		tinjyu	Cave (IOI13_cave)	C++14	100 / 100	1114 ms	760 KiB

cave

#include "cave.h"
#include <iostream>
#include <vector>
using namespace std;
long long int n,tag[100005];
bool tmpans[10005];
int ans[10005];
int find(int x)
{
	int con[n];
	for(int i=0;i<n;i++)
	{
		if(tag[i]==0)con[i]=0;
		else con[i]=tmpans[i];
	}
	//cout<<x<<endl;
	long long int c=tryCombination(con);
	//cout<<c<<endl;
	long long int mid,l=0,r=n-1,p;
	while(l<=r)
	{
		for(int i=0;i<n;i++)
		{
			if(tag[i]==0)con[i]=0;	
		}
		mid=(l+r)/2;
		for(int i=l;i<=mid;i++)
		{
			if(tag[i]==0)con[i]=1;
		}
		long long int tmp=tryCombination(con);
		//cout<<l<<" "<<mid<<endl;
		//for(int i=0;i<n;i++)cout<<con[i]<<" ";
		//cout<<tmp<<endl;
		if(c==x)
		{
			if(tmp==x)
			{
				l=mid+1;
			}
			else
			{
				r=mid-1;
				p=mid;
			}
		}
		else
		{
			if(tmp==x)
			{
				r=mid-1;
				p=mid;
			}
			else l=mid+1;
		}
	}
	//cout<<p<<endl;
	tag[p]=1;
	ans[p]=x;
	if(c==x)
	{
		tmpans[p]=1;
	}
	else tmpans[p]=0;
}
void exploreCave(int N) {
    n=N;
    for(int i=0;i<n;i++)
    {
    	find(i);
	}
    int ans1[n];
	int ans2[n];
    for(int i=0;i<n;i++)ans1[i]=tmpans[i];
    for(int i=0;i<n;i++)ans2[i]=ans[i];
    answer(ans1,ans2);
}

Compilation message (stderr)

cave.cpp: In function 'int find(int)':
cave.cpp:65:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
cave.cpp:62:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   tmpans[p]=1;
   ~~~~~~~~~^~

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