Submission #59268

#	Time	Username	Problem	Language	Result	Execution time	Memory
59268		TadijaSebez	Cave (IOI13_cave)	C++11	100 / 100	610 ms	640 KiB

cave

#include "cave.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
const int N=5005;
int id[N],ty[N];
int mask[N],n,good[N],k[N];
bool done[N];
/*int lid[N],tid[N];
int ok[N];
int tryCombination(int a[])
{
	int i;
	for(i=0;i<n;i++) ok[lid[i]]=a[i]==tid[i];
	for(i=0;i<n;i++) if(!ok[i]) return i;
	return -1;
}
void answer(int a[], int id[])
{
	int i;
	for(i=0;i<n;i++) printf("%i ",a[i]);printf("\n");
	for(i=0;i<n;i++) printf("%i ",id[i]);printf("\n");
}*/
int get(int a[]){ int x=tryCombination(a);if(x==-1) return n;return x;}
void exploreCave(int N)
{
	n=N;
	int x=get(mask),y;
	int i,j;
	for(i=0;i<n;i++)
	{
		mask[i]=1;
		y=get(mask);
		if(y<x)
		{
			id[i]=y,ty[i]=0,done[i]=1,good[i]=0;
			//printf("1:%i:%i %i\n",i,ty[i],id[i]);
		}
		mask[i]=0;
	}
	vector<int> pos,tmp[2];
	bool ok=1;
	for(i=x;i<n;i++)
	{
		pos.clear();
		for(j=0;j<n;j++) if(!done[j]) pos.pb(j);
		while(pos.size()>1)
		{
			tmp[0].clear();tmp[1].clear();
			for(j=0;j<pos.size();j++) tmp[j&1].pb(pos[j]);
			for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
			y=get(good);
			if(ok)
			{
				if(y>i) pos=tmp[0];
				else pos=tmp[1];
			}
			else
			{
				if(y>i) pos=tmp[1];
				else pos=tmp[0];
			}
			for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
		}
		id[pos[0]]=i;
		ty[pos[0]]=good[pos[0]]=ok;
		y=get(good);
		done[pos[0]]=1;
		if(y>i+1) ok=0;
		else ok=1;
		//printf("2:%i:%i %i\n",pos[0],ty[pos[0]],id[pos[0]]);
	}
	answer(ty,id);
}
/*int main()
{
	int n,i;
	scanf("%i",&n);
	for(i=0;i<n;i++) scanf("%i",&tid[i]);
	for(i=0;i<n;i++) scanf("%i",&lid[i]);
	exploreCave(n);
	return 0;
}*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<pos.size();j++) tmp[j&1].pb(pos[j]);
            ~^~~~~~~~~~~
cave.cpp:52:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
            ~^~~~~~~~~~~~~~
cave.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<tmp[0].size();j++) good[tmp[0][j]]^=1;
            ~^~~~~~~~~~~~~~

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