Submission #295782

#	Time	Username	Problem	Language	Result	Execution time	Memory
295782		Ahmad_Hasan	Cave (IOI13_cave)	C++17	100 / 100	426 ms	636 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

void exploreCave(int n){
    vector<int>fnd(n,-1);
    vector<int>kys(n,-1);
    vector<int>stt(n,-1);
    int s2[n],d[n];
    memset(s2,-1,sizeof(s2));
    memset(d,-1,sizeof(d));
    for(int i=0;i<n;i++){
        int s[n];
        for(int j=0;j<n;j++){
            if(d[j]!=-1){
                s[j]=s2[j];
            }else
            s[j]=1;
        }
        int inp;

        inp=tryCombination(s);
        int st;
        if(inp>i||inp==-1){
            st=1;
        }else{
            st=0;
        }
        stt[i]=st;

        int l=0,r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            for(int j=l;j<=mid;j++){
                if(d[j]!=-1){
                    s[j]=s2[j];
                }else{
                    s[j]=st;
                }
            }
            for(int j=mid+1;j<=r;j++){
                if(d[j]!=-1){
                    s[j]=s2[j];
                }else{
                    s[j]=!st;
                }
            }
            inp=tryCombination(s);
            int nst;
            if(inp>i||inp==-1){
                r=mid;
            }else{
                l=mid+1;
            }
            if(l==r){
                fnd[i]=l;
                d[l]=i;
                s2[l]=st;
                break;
            }

        }
    }
    answer(s2,d);
}


/***
8
5
3 1
7 0
6 4
0 5
5 7
*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:50:17: warning: unused variable 'nst' [-Wunused-variable]
   50 |             int nst;
      |                 ^~~

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