Submission #709018

#	Time	Username	Problem	Language	Result	Execution time	Memory
709018		aggrovector	Cave (IOI13_cave)	C++17	100 / 100	1306 ms	468 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,j;

void exploreCave(int N) {
    int s[N],d[N],vi[N],anss[N],ansd[N];
    for (i=0;i<N;i++) {
    	s[i]=0;
    	vi[i]=0;
    	anss[i]=0;
    	ansd[i]=0;
	}
	for (j=0;j<N;j++) {
		for (i=0;i<N;i++) {
			if (vi[i]==1) {
				s[i]=anss[i];
			}
			else {
				s[i]=0;
			}
		}
		x=tryCombination(s);
		if (x==-1) {
			x=N;
		}
		if (x<=j) { //jth door is closed when switch is 0
			type=1;
		}
		else { //jth door is open when switch is 0
			for (i=0;i<N;i++) {
				if (vi[i]==1)  {
					s[i]=anss[i];
				}
				else {
					s[i]=1;
				}
			}
			type=2;
			x=j;
		}
		l=0;
		r=N-1;
		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==-1) {
				y=N;
			}
			for (i=0;i<N;i++) {
				if (vi[i]==0) {
					if (type==1) {
						s[i]=0;
					}
					else {
						s[i]=1;
					}
				}
			}
			if (y==x) {
				l=mid+1;
			}
			else {
				r=mid;
			}
		}
		vi[l]=1;
		ansd[l]=j;
		if (type==1) {
			anss[l]=1;
		}
		else {
			anss[l]=0;
		}
	}
	answer(anss,ansd);
}	

#endif /* __CAVE_H__ */

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:21:14: warning: unused variable 'd' [-Wunused-variable]
   21 |     int s[N],d[N],vi[N],anss[N],ansd[N];
      |              ^

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