Submission #1024147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024147		Nonoze	Cave (IOI13_cave)	C++17	100 / 100	228 ms	1112 KiB

cave

    #include "cave.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    void exploreCave(int N) {
    	vector<int> S(N, 0), D(N, -1);
    	for (int i = 0; i < N; ++i)
    	{
    		int remplacer=1;
    		int tryc=tryCombination(S.data());
    		if (tryc>i || tryc==-1) {
    			for (int j = 0; j < N; ++j)
    			{
    				if (D[j]==-1)
    				{
    					S[j]=1;
    				}
    			}
    			remplacer=0;
    		}
    		vector<int> s_new=S;
    		int l=0, r=N-1;
    		while(l<r) {
    			int mid=(l+r)/2;
    			for (int j = l; j <= mid; ++j)
    			{
    				if (D[j]==-1)
    				{
    					s_new[j]=remplacer;
    				}
    			}
    			int tryc=tryCombination(s_new.data());
    			if (tryc>i || tryc==-1) {
    				r=mid;
    			}
    			else {
    				l=mid+1;
    			}
    			s_new=S;
    		}
    		S[l]=remplacer;
    		D[l]=i;
    		for (int j = 0; j < N; ++j)
    		{
    			if (D[j]==-1)
    			{
    				S[j]=0;
    			}
    		}
    	}
    	answer(S.data(), D.data());
    }

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