Submission #653903

#	Time	Username	Problem	Language	Result	Execution time	Memory
653903		AbdelmagedNour	Cave (IOI13_cave)	C++17	100 / 100	372 ms	612 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int N=5005;
int s[N],d[N],done[N],now;
bool check(int md){
    for(int i=0;i<=md;i++)s[i]^=(!done[i]);
    int x=tryCombination(s);
    for(int i=0;i<=md;i++)s[i]^=(!done[i]);
    return x>now||x==-1;
}
void exploreCave(int n){
    for(int i=0;i<n;i++){
        now=i;
        int x=tryCombination(s);
        for(int j=0;j<n&&(x>i||x==-1);j++)s[j]^=(!done[j]);
        int l=0,r=n-1,ans;
        while(l<=r){
            int md=(l+r)>>1;
            if(check(md))r=(ans=md)-1;
            else l=md+1;
        }
        d[ans]=i;
        done[ans]=1;
        s[ans]^=1;
    }
    answer(s,d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:25:15: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |         s[ans]^=1;
      |         ~~~~~~^~~

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