Submission #708911

#	Time	Username	Problem	Language	Result	Execution time	Memory
708911		aggrovector	Cave (IOI13_cave)	C++17	0 / 100	170 ms	412 KiB

cave

#ifndef __CAVE_H__
#define __CAVE_H__

#ifdef __cplusplus
extern "C" {
#endif

int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);

#ifdef __cplusplus
}
#endif

#include <bits/stdc++.h>
using namespace std;
int i,l,r,x,mid,unlocked,type,y;
void exploreCave(int N) {
	int s[N],vi[N],anss[N],ansd[N];
    for (i=0;i<N;i++) {
    	s[i]=0;
    	vi[i]=0;
	}
	type=1;
	while(unlocked<N) {
		for (i=0;i<N;i++) {
			if (vi[i]==1) {
				s[i]=anss[i];
			}
			else {
				if (type==1) {
					s[i]=0;
				}
				else {
					s[i]=1;
				}
			}
		}
		l=0;
		r=N-1;
		x=tryCombination(s);
		if (x==-1) {
			if (type==1) {
				type=2;
				continue;
			}
			else {
				break;
			}
		}
		while(l<r) {
			mid=(l+r)/2;
			for (i=0;i<=mid;i++) {
				if (vi[i]==0) {
					if (type==1) {
						s[i]=1;
					}
					else {
						s[i]=0;
					}
				}
			}
			y=tryCombination(s);
			if (y==x) {
				l=mid+1;
			}
			else {
				for (i=0;i<=mid;i++) {
					if (vi[i]==0) {
						s[i]=0;
					}
				}
				r=mid;
			}
		}
		vi[l]=1;
		ansd[l]=x;
		if (type==1) {
			anss[l]=1;
		}
		else {
			anss[l]=0;
		}
		unlocked++;
	}
	answer(anss,ansd);
}

#endif /* __CAVE_H__ */

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