Submission #348083

#	Time	Username	Problem	Language	Result	Execution time	Memory
348083		laoriu	Cave (IOI13_cave)	C++14	100 / 100	847 ms	748 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define pb push_back
using namespace std;
const int MAX=5005;
int ok[MAX];
int S[MAX],D[MAX];
void exploreCave(int n){

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)if(!D[j])
                    S[j]=0;
                else S[j]=ok[j];
        int x=tryCombination(S);
        if(x==i){
            int ans;
            int b=0,e=n-1;
            while(b<=e){
                int m=b+e>>1;
                for(int j=0;j<n;j++)if(!D[j])
                    S[j]=(j<=m);
                else S[j]=ok[j];
                int x=tryCombination(S);
                if(x==i)b=m+1;
                else{
                    e=m-1;
                    ans=m;
                }
            }
            D[ans]=i+1;
            ok[ans]=1;
        }
        else{
            int ans;
            int b=0,e=n-1;
            while(b<=e){
                int m=b+e>>1;
                for(int j=0;j<n;j++)if(!D[j])
                    S[j]=(j>m);
                else S[j]=ok[j];
                int x=tryCombination(S);
                if(x==i)b=m+1;
                else{
                    e=m-1;
                    ans=m;
                }
            }
            D[ans]=i+1;
            ok[ans]=0;
        }

    }
    for(int i=0;i<n;i++) D[i]--;
    answer(ok,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:20:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |                 int m=b+e>>1;
      |                       ~^~
cave.cpp:38:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |                 int m=b+e>>1;
      |                       ~^~
cave.cpp:50:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |             ok[ans]=0;
      |             ~~~~~~~^~
cave.cpp:32:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |             ok[ans]=1;
      |             ~~~~~~~^~

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