Submission #917046

#	Time	Username	Problem	Language	Result	Execution time	Memory
917046		manishjha91	Cave (IOI13_cave)	C++17	100 / 100	301 ms	600 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
void exploreCave(int n) {
    
    int a[n];
    memset(a,0,sizeof a);
    int d[n];
    for(int i=0; i<n; i++) d[i] = i;
    
	int done[n];
	memset(done,0,sizeof done);
	int x;
    for(int i=0; i<n; i++)
    {
    	for(int j=0; j<n; j++)
    	{
    		if(!done[j])
    		{
    			a[j] = 0;
    		}
    	}
    	
    	x = tryCombination(a);
    	if(x<0 || x>i)
    	{
    		for(int j=0; j<n; j++)
    		{
    			if(!done[j]) a[j] = 1;
    		}
    	}
    	
		int l = 0;
		int r = n-1;
		int ans = n-1;
		while(l<=r)
		{
			int mid = l + (r-l)/2;
			
			for(int j=l; j<=mid; j++)
			{
				if(!done[j])
				{
					a[j]^=1;
				}
			}
			x = tryCombination(a);
			if(x<0 || x>i)
			{
				for(int j=l; j<=mid; j++)
				{
					if(!done[j]) a[j]^=1;
				}
				ans = mid;
				r = mid-1;
			}
			else l = mid + 1;
		}
		done[ans] = 1;
		d[ans] = i;
		a[ans]^=1;
    }
    
    
    
    // int i=tryCombination(a);
    // while(i!=-1)
    // {
    	// a[d[i]] ^=1;
    	// i = tryCombination(a);
    // }
    answer(a,d);
}

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